Submission #288220

#	Time	Username	Problem	Language	Result	Execution time	Memory
288220		kig9981	Factories (JOI14_factories)	C++17	100 / 100	6485 ms	166676 KiB

factories

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

vector<pair<int,int>> adj[500000];
int query_num, root, P[500000], W[500000], num[500000], cnt[500000];
long long V[500000], dist[500000][19];
bool chk[500000];

void reset(int c)
{
	W[c]=0;
	for(auto[n,w]: adj[c]) if(!chk[n] && W[n]) reset(n);
}

int dfs(int c)
{
	W[c]=1; V[c]=-1;
	for(auto[n,w]: adj[c]) if(!chk[n] && W[n]==0) W[c]+=dfs(n);
	return W[c];
}

int dfs2(int c, int v)
{
	for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>v) return dfs2(n,v);
	return c;
}

void dfs3(int c)
{
	dist[c][cnt[c]++]=V[c];
	for(auto[n,w]: adj[c]) if(!chk[n] && V[n]==-1) {
		V[n]=V[c]+w;
		dfs3(n);
	}
}

int get_centroid(int c)
{
	reset(c);
	chk[c=dfs2(c,dfs(c))]=true;
	dist[c][cnt[c]++]=V[c]=0;
	for(auto[n,w]: adj[c]) if(!chk[n]) {
		V[n]=w; dfs3(n);
		P[get_centroid(n)]=c;
	}
	return c;
}

void Init(int N, int *A, int *B, int *D)
{
	for(int i=0;i<N-1;i++) {
		adj[A[i]].emplace_back(B[i],D[i]);
		adj[B[i]].emplace_back(A[i],D[i]);
	}
	root=get_centroid(0);
}

long long Query(int S, int *X, int T, int *Y)
{
	long long ret=0x7fffffffffffffffLL;
	int v; ++query_num;
	for(int i=0;i<S;i++) {
		v=cnt[X[i]];
		for(int j=X[i];j!=root;j=P[j]) {
			if(num[j]==query_num) V[j]=min(V[j],dist[X[i]][--v]);
			else {
				num[j]=query_num;
				V[j]=dist[X[i]][--v];
			}
		}
		if(num[root]==query_num) V[root]=min(V[root],dist[X[i]][--v]);
		else {
			num[root]=query_num;
			V[root]=dist[X[i]][--v];
		}
	}
	for(int i=0;i<T;i++) {
		v=cnt[Y[i]];
		for(int j=Y[i];j!=root;j=P[j]) {
			v--;
			if(num[j]!=query_num) continue;
			ret=min(ret,V[j]+dist[Y[i]][v]);
		}
		ret=min(ret,V[root]+dist[Y[i]][--v]);
	}
	return ret;
}

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