Editorial for Tổ chức đối lập


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const fi='';
      fo='';
      maxn=10001;
var n,k,re:longint;
    b,sl,pos,cur:array[1..maxn] of longint;
    a:array[1..maxn shl 1] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi); reset(input);
     read(k,n);
     for i:=1 to n-1 do
     begin
          read(b[i]);
          inc(sl[b[i]]);
     end;
     pos[1]:=1; cur[1]:=1;
     for i:=2 to n+1 do
     begin
          pos[i]:=pos[i-1]+sl[i-1];
          cur[i]:=pos[i];
     end;
     for i:=1 to n-1 do
     begin
          a[cur[b[i]]]:=i+1;
          inc(cur[b[i]]);
     end;
     close(input);
end;

function dfs(x:longint):longint;
var i,r:longint;
begin
     r:=1;
     for i:=pos[x] to pos[x+1]-1 do
         r:=r+dfs(a[i]);
     if r>=k then
     begin
          r:=0;
          inc(re);
     end;
     dfs:=r;
end;

procedure pr;
var i:longint;
begin
     re:=0;
     i:=dfs(1);
end;

procedure wf;
begin
     assign(output,fo); rewrite(output);
     writeln(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 10005

int a[N], n, k, d[N];
//a[i] = lowest ancestor of i
//d[i] = number of decestor of i

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    scanf("%d%d",&k,&n); a[1] = 0;
    fo(i,2,n) {
        scanf("%d",a+i);
        for(int j = a[i]; j; j = a[j]) ++d[j];
    }
    int res = 0;
    fod(i,n,1) if( d[i] + 1 >= k ) {
        ++res;
        for(int j = a[i]; j; j = a[j]) d[j] -= d[i]+1;
    }
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

program v8org;
uses    math;
const   maxn=12345;
        fi='';
var     adj,link:array[1..maxn] of longint;
        head,f:array[1..maxn] of longint;
        k,n,m,res:longint;

procedure input;
var     inp:text;
        i,p:longint;
begin
        assign(inp,fi);reset(inp);
        readln(inp,k);readln(inp,n);
        for i:=2 to n do
        begin
                read(inp,p);
                inc(m);
                adj[m]:=i;
                link[m]:=head[p];
                head[p]:=m;
        end;
        close(inp);
end;

procedure dfs(i:longint);
var     j:longint;
begin
        if head[i]=0 then
        begin
                if k>1 then
                f[i]:=1
                else
                begin
                        f[i]:=0;
                        inc(res);
                end;
                exit;
        end;
        j:=head[i];
        f[i]:=1;
        while j<>0 do
        begin
                dfs(adj[j]);
                inc(f[i],f[adj[j]]);
                j:=link[j];
        end;
        if f[i]>=k then
        begin
                f[i]:=0;
                inc(res);
        end;
end;

begin
        input;
        dfs(1);
        write(res);
end.

Code mẫu của RR

PROGRAM V8ORG;
CONST
  fi='';
  fo='';
  maxn=10000;
VAR
  n,k:integer;
  sc:array[1..maxn] of integer;
  son:array[1..maxn,1..maxn] of integer;
  sl:array[1..maxn] of integer;
  dd:integer;
Procedure ReadInput;
Var
  f:text;
  u,i:integer;
Begin
  Assign(f,fi); Reset(f);
  Readln(f,k);
  Readln(f,n);
  For i:=2 to n do
    begin
      Read(f,u);
      inc(sc[u]);
      son[u,sc[u]]:=i;
    end;
End;
Procedure DFS(u:integer);
Var
  i,v:integer;
Begin
  sl[u]:=1;
  For i:=1 to sc[u] do
    begin
      v:=son[u,i];
      DFS(v);
      sl[u]:=sl[u]+sl[v];
    end;
  If sl[u]>=k then
  begin
    inc(dd);
    sl[u]:=0;
  end;
End;
Procedure WriteOutput;
Var
  f:text;
Begin
  Assign(f,fo); Rewrite(f);
  Writeln(f,dd);
  Close(f);
End;
BEGIN
  ReadInput;
  DFS(1);
  WriteOutput;
END.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 100111
#define oo 1111111111
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,k,cha[11111],d[11111],x,KQ=0;

int main(){
     //freopen("V8ORG.in","r",stdin);
     scanf("%d %d",&k,&n);
     for(int i = 2;i<=n;i++){
           scanf("%d",&cha[i]);
           d[i] = 0;
           x = i;
           do{
                x = cha[x];
                d[x]++;
           }while(x!=1);
     }
     cha[1] = 1;
    // for(int i = 1;i<=n;i++) printf("%d %d\n",i,cha[i]);getch();
     for(int i = n;i>=1;i--){
           if(d[i]>=k-1){
                KQ++;       
                x = i;
                do{
                    // printf("%d\n",x);
                     x = cha[x];
                     d[x] -= (d[i]+1); 
                }while(x!=1);
           }  
     }

     printf("%d",KQ);
    // getch();
}

Code mẫu của ll931110

{$MODE DELPHI}
program V8ORG;
const
  input  = '';
  output = '';
  maxn = 10000;
type
  pnode = ^tnode;
  tnode = record
    val: integer;
    link: pnode;
  end;
var
  n,k,count: integer;
  d,t,pre: array[1..maxn] of integer;
  dep: array[1..maxn] of pnode;

procedure add(i,x: integer);
var
  p: pnode;
begin
  new(p);
  p^.val := x;
  p^.link := dep[i];
  dep[i] := p;
end;

procedure init;
var
  f: text;
  i: integer;
begin
  assign(f, input);
    reset(f);

  read(f, k, n);
  t[1] := 1;
  d[1] := 0;
  for i := 1 to n do dep[i] := nil;

  for i := 2 to n do
    begin
      read(f, pre[i]);
      t[i] := 1;
      d[i] := d[pre[i]] + 1;
      add(d[i],i);
    end;

  close(f);
end;

procedure solve;
var
  v,i: integer;
  p: pnode;
begin
  for i := n downto 1 do
    begin
      p := dep[i];
      while p <> nil do
        begin
          v := p^.val;
          if t[v] >= k then inc(count) else t[pre[v]] := t[pre[v]] + t[v];
          p := p^.link;
        end;
    end;

  if t[1] >= k then inc(count);
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, count);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của khuc_tuan

type
    PNode = ^Node;
    Node = record
         i : integer;
         next : PNode;
        end;
var
   n, k, res : integer;
   ke : array[1..10000] of PNode;

   function dfs(i : integer) : integer;
   var p : PNode;
   sc, j : integer;
   begin
       p := ke[i];
        sc := 1;
       while p<>nil do begin
             j := p^.i;
             sc := sc + dfs(j);
             p := p^.next;
       end;
       if sc>=k then begin
         inc(res);
         sc := 0;
        end;
        dfs := sc;
   end;

var
   p : PNode;
   i,x : integer;
begin
     read( k, n);
     for i:=2 to n do begin
         read(x);
         new(p);
         p^.i := i;
         p^.next := ke[x];
         ke[x] := p;
     end;
     res := 0;
     dfs(1);
     writeln( res);
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.