Submission #86981

#	Time	Username	Problem	Language	Result	Execution time	Memory
86981		wzy	Factories (JOI14_factories)	C++11	100 / 100	5289 ms	261344 KiB

factories

#include <bits/stdc++.h>

#include"factories.h"

using namespace std;

#define ll long long
const int N = 500005;

vector< array<int, 2 > > adj[N];
int paiC[N];
bool blocked[N];
int sz[N];
ll vl[N];
ll maxint = 1000000000000000000ll;
int n;
ll dist[N][20];
int layer[N];
void computa(int x , int y){
	sz[x] = 1;
	for(auto w : adj[x]){
		if(blocked[w[0]] || y == w[0]) continue;
		computa(w[0] , x);
		sz[x] += sz[w[0]];
	}
}

int find_C(int x , int y , int root){
	int centroid = x;
	for(auto w : adj[x]){
		if(blocked[w[0]] || y == w[0]) continue;
		if(sz[w[0]] > sz[root]/2) centroid = find_C(w[0] , x , root);
	}
	return centroid;
}

void fill_dp(int x , int y , int pai , int root , ll dis){
	dist[x][layer[root]] = dis;
	for(auto w : adj[x]){
		if(blocked[w[0]] || y == w[0]) continue;
		fill_dp(w[0] , x , pai, root ,(ll)dis + 1ll*w[1]);
	}
}


void decompose(int x  = 0, int pai = -1){
	computa(x , x);
	x = find_C(x , x , x);
	paiC[x] = pai;
	if(pai == -1) layer[x] = 0;
	else layer[x] = layer[pai] + 1;
	fill_dp(x , x , pai , x,0);
	blocked[x] = true;
	for(auto w : adj[x]){
		if(!blocked[w[0]])
		decompose(w[0] , x);
	}
}



void Init(int N, int A[], int B[], int D[]){
	for(int i = 0 ; i < N - 1 ; i ++){
		adj[A[i]].push_back({B[i] , D[i]});
		adj[B[i]].push_back({A[i] , D[i]});
	}
	n = N;
	decompose();
	for(int i = 0 ; i < N ; i ++){
		vl[i] = maxint;
	} 
}

long long Query(int S, int X[], int T, int Y[]){
	for(int i = 0 ; i < S ; i ++){
		ll currdis = 0;
		int x = X[i];
		while(x != -1){
			vl[x] = min(vl[x] , dist[X[i]][layer[x]]);
			x = paiC[x];
		}
	}
	ll ans = maxint;
	for(int i = 0 ; i < T ; i ++){
		ll currdis = 0;
		int x = Y[i];
		while(x != -1){
			ans = min(ans , dist[Y[i]][layer[x]] + vl[x]);
			x = paiC[x];
		}
	}
	for(int i = 0 ; i < S ; i ++){
		int x = X[i];
		while(x != -1){
			vl[x] = maxint;
			x = paiC[x];
		}
	}	
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:76:6: warning: unused variable 'currdis' [-Wunused-variable]
   ll currdis = 0;
      ^~~~~~~
factories.cpp:85:6: warning: unused variable 'currdis' [-Wunused-variable]
   ll currdis = 0;
      ^~~~~~~

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