Submission #1165732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165732		_rain_	Factories (JOI14_factories)	C++17	100 / 100	2926 ms	336176 KiB

factories

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

const int N=(int)1e6;
const int MAXLOG=19;
const LL INF=1e18+7;
vector<pair<int,int>>ke[N+2];
#define fi first
#define se second

void add_canh(int u,int v,int c){
	ke[u].push_back({v,c}),ke[v].push_back({u,c});
	return;
}


class Centroid{
	private:
		vector<int>par,sub;
		vector<LL>mx;
		vector<bool>del;
		vector<LL>d;
		vector<vector<pair<int,LL>>>pr;
	public:
		
		void init_size(int _n){
			par.resize(_n+2,0);
			sub.resize(_n+2,0);
			del.resize(_n+2,0);
			mx.resize(_n+2,INF);
			d.resize(_n+2,INF);
			pr.resize(_n+2);
		}
		
		void dfs(int u,int p){
			sub[u]=1;
			for(auto&v:ke[u]){
				if (v.fi==p || del[v.fi]) continue;
				dfs(v.fi,u);
				sub[u]+=sub[v.fi];
			}
		}
		void redfs(int u,int p,int root,LL dis){
			pr[u].push_back({root,dis});
			for(auto&v:ke[u]){
				if (v.fi==p||del[v.fi]) continue;
				redfs(v.fi,u,root,dis+v.second);
			}
		}
		
		int Find_centroid(int u,int p,int half){
			for(auto&v:ke[u]){
				if (del[v.fi]||v.fi==p) continue;
				if (sub[v.fi]>half) return Find_centroid(v.fi,u,half);
			}
			return u;
		}
		
		void build_centroid(int u,int p){
			dfs(u,u);
			u=Find_centroid(u,u,sub[u]/2);
			redfs(u,u,u,0);
			del[u]=true;
			for(auto&v:ke[u]) if (del[v.fi]==0) build_centroid(v.fi,u);
		}
		
		void add(int u){
			for(auto&x:pr[u]){
				mx[x.first]=min(mx[x.first],x.second);
			}
		}
		void era(int u){
			for(auto&x:pr[u]){
				mx[x.first]=INF;
			}
		}
		LL Find(int u){
			LL ans=INF;
			for(auto&x:pr[u]){
				ans=min(ans,mx[x.first]+x.second);
			}
			return ans;
		}
};
Centroid tree;

void Init(int n,int a[],int b[],int d[]){
	for(int i=0;i<n-1;++i){
		++a[i],++b[i];
		add_canh(a[i],b[i],d[i]);
	}
	tree.init_size(n);
	tree.build_centroid(1,0);

	return;
}
long long Query(int s,int x[],int t,int y[]){
	LL ans=INF;
	for(int i=0;i<s;++i) ++x[i];
	for(int i=0;i<t;++i) ++y[i];
	for(int i=0;i<s;++i) tree.add(x[i]);
	for(int i=0;i<t;++i) ans=min(ans,tree.Find(y[i]));
	for(int i=0;i<s;++i) tree.era(x[i]);
	return ans;
}

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