Submission #673406

#	Time	Username	Problem	Language	Result	Execution time	Memory
673406		dsyz	Factories (JOI14_factories)	C++17	100 / 100	4189 ms	292056 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
#define MAXN (1000005)
vector<pair<ll,ll> > v[MAXN];
ll sub[MAXN];
ll par[MAXN];
ll lvl[MAXN];
ll dist[MAXN][20];
ll m[MAXN];
ll dfs1(ll x,ll p,ll l){
	sub[x] = 1;
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1){ //unvisited
			sub[x] += dfs1(u.first,x,l);
		}
	}
	return sub[x];
}
ll dfs2(ll x,ll p,ll siz){ //siz is total size of this centroid tree 
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1 && sub[u.first] > siz / 2){
			return dfs2(u.first,x,siz); //remember that siz remains constant
		}
	}
	return x;
}
void dfsdist(ll x,ll p,ll curlvl,ll curdist){
	dist[x][curlvl] = curdist;
	for(auto u : v[x]){
		if(u.first != p && lvl[u.first] == -1){ //unvisited
			dfsdist(u.first,x,curlvl,curdist + u.second);
			//Note: curlvl is unchanged since we are moving down so
			//the relative lvl has already changed
		}
	}
}
void build(ll x,ll p,ll l){
	ll siz = dfs1(x,p,l);
	ll cent = dfs2(x,p,siz);
	if(p == -1) p = cent;
	par[cent] = p;
	lvl[cent] = l;
	dfsdist(cent,-1,l,0);
	for(auto u : v[cent]){
		if(lvl[u.first] == -1){ //unvisited
			build(u.first,cent,l + 1);
		}
	}
}

void Init(int N, int A[], int B[], int D[]) {
	for(ll i = 0;i < N - 1;i++){
		v[A[i]].push_back(make_pair(B[i],D[i]));
		v[B[i]].push_back(make_pair(A[i],D[i]));
	}
	for(ll i = 0;i < MAXN;i++){
		for(ll j = 0;j < 20;j++){
			dist[i][j] = 1e18;
		}
	}
	memset(lvl,-1,sizeof(lvl)); //need lvl to find dist[i][lvl]
	build(0,-1,0);
	for(ll i = 0;i < MAXN;i++){
		m[i] = 1e18;
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	for(ll i = 0;i < S;i++){
		ll curlevel = lvl[X[i]];
		ll x = X[i];
		while(curlevel >= 0){
			m[x] = min(m[x],dist[X[i]][curlevel]);
			x = par[x];
			curlevel--;
		}
	}
	ll ans = 1e18;
	for(ll i = 0;i < T;i++){
		ll curlevel = lvl[Y[i]];
		ll y = Y[i];
		while(curlevel >= 0){
			ans = min(ans,m[y] + dist[Y[i]][curlevel]);
			y = par[y];
			curlevel--;
		}
	}
	for(ll i = 0;i < S;i++){ //undo, prepare for next query
		ll curlevel = lvl[X[i]];
		ll x = X[i];
		while(curlevel >= 0){
			m[x] = 1e18;
			x = par[x];
			curlevel--;
		}
	}
	return ans;
}

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