Submission #10096

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
10096	2014-10-13 04:53:52	cki86201	Factories (JOI14_factories)	C++98	100 / 100	4376 ms	185964 KiB

factories

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "factories.h"
const int N_ = 500050;
int up[N_][20];
long long ul[N_][20];
int st[N_], en[N_<<1], len[N_<<1], nxt[N_<<1];
inline void addE(int s,int e,int l,int c){nxt[c]=st[s],st[s]=c,en[c]=e,len[c]=l;}
int chk[N_], down[N_];
void dfs_p(int x,int fa){
  down[x] = 1;
  for(int i=st[x];i;i=nxt[i])if(en[i] != fa && !chk[en[i]])dfs_p(en[i], x), down[x] += down[en[i]];
}
void dfs_l(int x,int fa,int cnt,int p){
  for(int i=st[x];i;i=nxt[i])if(en[i] != fa && !chk[en[i]])up[en[i]][cnt] = p, ul[en[i]][cnt] = ul[x][cnt] + len[i], dfs_l(en[i], x, cnt, p);
}
void Decomp(int x, int depth){
  int half = down[x] / 2;
  for(;;){
    int i;
    for(i=st[x];i;i=nxt[i]){
      if(!chk[en[i]] && down[en[i]] < down[x] && down[en[i]] > half)break;
    }
    if(!i)break;
    x = en[i];
  }
  up[x][depth] = x;
  dfs_l(x, -1, depth, x);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67