oj.uz

Submission #10096

# Submission time Handle Problem Language Result Execution time Memory
10096 2014-10-13T04:53:52 Z cki86201 Factories (JOI14_factories) C++
100 / 100
 4376 ms 185964 KB 
#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);
	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 165948 KB Output is correct
2 Correct 380 ms 165948 KB Output is correct
3 Correct 412 ms 165948 KB Output is correct
4 Correct 380 ms 165948 KB Output is correct
5 Correct 412 ms 166036 KB Output is correct
6 Correct 304 ms 165948 KB Output is correct
7 Correct 412 ms 165948 KB Output is correct
8 Correct 396 ms 165948 KB Output is correct
9 Correct 404 ms 166036 KB Output is correct
10 Correct 288 ms 165948 KB Output is correct
11 Correct 404 ms 165948 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 165948 KB Output is correct
2 Correct 2016 ms 165948 KB Output is correct
3 Correct 3048 ms 168552 KB Output is correct
4 Correct 752 ms 165948 KB Output is correct
5 Correct 3936 ms 185964 KB Output is correct
6 Correct 3064 ms 168228 KB Output is correct
7 Correct 884 ms 166324 KB Output is correct
8 Correct 536 ms 165948 KB Output is correct
9 Correct 960 ms 169732 KB Output is correct
10 Correct 892 ms 166284 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2344 ms 165948 KB Output is correct
2 Correct 2396 ms 165948 KB Output is correct
3 Correct 3484 ms 168128 KB Output is correct
4 Correct 3508 ms 168244 KB Output is correct
5 Correct 3504 ms 168144 KB Output is correct
6 Correct 4376 ms 185352 KB Output is correct
7 Correct 1064 ms 165948 KB Output is correct
8 Correct 3404 ms 168120 KB Output is correct
9 Correct 3452 ms 168124 KB Output is correct
10 Correct 3496 ms 168136 KB Output is correct
11 Correct 984 ms 169728 KB Output is correct
12 Correct 544 ms 165948 KB Output is correct
13 Correct 736 ms 165948 KB Output is correct
14 Correct 740 ms 165948 KB Output is correct
15 Correct 884 ms 166284 KB Output is correct
16 Correct 912 ms 166284 KB Output is correct