Submission #296712

#	Time	Username	Problem	Language	Result	Execution time	Memory
296712		b00n0rp	Factories (JOI14_factories)	C++17	15 / 100	8052 ms	118380 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define pii pair<int,int>
#define F first
#define S second
#define vi vector<int>
#define pb push_back
#define runtime() ((double)(clock())/CLOCKS_PER_SEC)

int n,centroid;
const int MAXN = 500005;
const ll INF = 1e16;

int par[MAXN][21],cenpar[MAXN];
int dep[MAXN],sz[MAXN];
vector<pii> adj[MAXN];
bitset<MAXN> vis;

vi g[MAXN];

ll mnd[MAXN],dist[MAXN];

void dfs0(int u){
	for(auto v:adj[u]){
		if(v.F != par[u][0]){
			par[v.F][0] = u;
			dep[v.F] = dep[u]+1;
			dist[v.F] = dist[u]+v.S;
			dfs0(v.F);
		}
	}
}

void dfs_sz(int u,int p){
	sz[u] = 1;
	for(auto v:adj[u]){
		if(v.F != p and vis[v.F] == 0){
			dfs_sz(v.F,u);
			sz[u] += sz[v.F];
		}
	}
}

int find_centroid(int u,int p,int tot){
	for(auto v:adj[u]){
		if(v.F == p or vis[v.F]) continue;
		if(sz[v.F] > tot/2) return find_centroid(v.F,u,tot); 
	}
	return u;
}

void centroid_decomposition(int u,int p){
	dfs_sz(u,u);
	int cen = find_centroid(u,p,sz[u]);
	if(p == -1) centroid = cen;
	else g[p].pb(cen);
	cenpar[cen] = p;
	vis[cen] = 1;
	for(auto v:adj[cen]){
		if(!vis[v.F]) centroid_decomposition(v.F,cen);
	}
}

int lca(int u,int v){
	if(dep[u] < dep[v]) swap(u,v);
	for(int i = 20; i >= 0; i --){
		if(dep[u]-(1<<i) >= dep[v]) u = par[u][i];
	}
	if(u == v) return u;
	for(int i = 20; i >= 0; i --){
		if(par[u][i] != par[v][i]){
			u = par[u][i];
			v = par[v][i];
		}
	}
	return par[u][0];
}

ll calc_dist(int u,int v){
	return dist[u]+dist[v]-2*dist[lca(u,v)];
}

void Init(int N, int A[], int B[], int D[]){
	n = N;
	REP(i,n-1){
		adj[A[i]].pb({B[i],D[i]});
		adj[B[i]].pb({A[i],D[i]});
	}
	par[0][0] = 0;
	dep[0] = 0;
	dfs0(0);
	FOR(j,1,21){
		REP(i,n){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}
	centroid_decomposition(0,-1);
	REP(i,n+1) mnd[i] = INF;
	// REP(i,n) cout << i << " " << cenpar[i] << endl;
}

void upd(int u,int type){
	int cur = u;
	int cnt = 0;
	while(cur != -1){
		cnt++;
		if(type == 0){
			mnd[cur] = min(mnd[cur],calc_dist(cur,u));
		}
		else mnd[cur] = INF;
		cur = cenpar[cur];
	}
	
	assert(cnt <= 20);
}

ll quer(int u){
	ll res = INF;
	int cur = u;
	int cnt = 0;
	while(cur != -1){
		cnt ++;
		res = min(res,calc_dist(u,cur)+mnd[cur]);
		cur = cenpar[cur];
	}
	assert(cnt <= 20);
	return res;
}

ll Query(int S, int X[], int T, int Y[]) {
	REP(i,S) upd(X[i],0);
	ll ans = INF;
	// REP(i,S) REP(j,T) ans = min(ans,calc_dist(X[i],Y[j]));
	REP(i,T) ans = min(ans,quer(Y[i]));
	REP(i,S) upd(X[i],1);
	return ans;
}

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