oj.uz

Submission #10095

# Submission time Handle Problem Language Result Execution time Memory
10095 2014-10-13T04:52:40 Z cki86201 Factories (JOI14_factories) C++
15 / 100
 3448 ms 162692 KB 
#include "factories.h"

const int N_ = 500050;
int up[N_][19];
long long ul[N_][19];
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);
	chk[x] = 1;
	for(int i=st[x];i;i=nxt[i]){
		if(chk[en[i]])continue;
		dfs_p(en[i], -1);
		Decomp(en[i], depth+1);
	}
}

void Init(int N, int A[], int B[], int D[]) {
	for(int i=0;i<N-1;i++)addE(A[i]+1, B[i]+1, D[i], i+i+1), addE(B[i]+1, A[i]+1, D[i], i+i+2);
	dfs_p(1, -1);
	Decomp(1, 0);
}

long long dis[N_][2];
int C;

void update(int p){
	for(int i=0;up[p][i];i++){
		int x = up[p][i];
		if(dis[x][1] != C)dis[x][1] = C, dis[x][0] = ul[p][i];
		else if(dis[x][0] > ul[p][i])dis[x][0] = ul[p][i];
	}
}

long long read(int p){
	long long ret = 5e13;
	for(int i=0;up[p][i];i++){
		int x = up[p][i];
		if(dis[x][1] == C && ret > dis[x][0] + ul[p][i])ret = dis[x][0] + ul[p][i];
	}
	return ret;
}

long long Query(int S, int X[], int T, int Y[]) {
	++C;
	for(int i=0;i<S;i++)update(X[i]+1);
	long long ans = 5e13;
	for(int i=0;i<T;i++){
		long long t = read(Y[i]+1);
		if(ans > t)ans = t;
	}
	return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 160088 KB Output is correct
2 Correct 364 ms 160088 KB Output is correct
3 Correct 396 ms 160088 KB Output is correct
4 Correct 376 ms 160088 KB Output is correct
5 Correct 400 ms 160172 KB Output is correct
6 Correct 268 ms 160088 KB Output is correct
7 Correct 396 ms 160088 KB Output is correct
8 Correct 392 ms 160088 KB Output is correct
9 Correct 400 ms 160168 KB Output is correct
10 Correct 284 ms 160088 KB Output is correct
11 Correct 396 ms 160088 KB Output is correct

Subtask #2
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 160088 KB Output is correct
2 Correct 1972 ms 160088 KB Output is correct
3 Incorrect 2988 ms 162692 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2272 ms 160088 KB Output is correct
2 Correct 2388 ms 160088 KB Output is correct
3 Incorrect 3448 ms 161948 KB Output isn't correct
4 Halted 0 ms 0 KB -