Submission #10096

#	Time	Username	Problem	Language	Result	Execution time	Memory
10096		cki86201	Factories (JOI14_factories)	C++98	100 / 100	4376 ms	185964 KiB

factories

#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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67