Submission #1106470

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106470		PieArmy	Factories (JOI14_factories)	C++17	100 / 100	2064 ms	233540 KiB

factories

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include "factories.h"
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n;
vector<pair<int,ll>>komsu[500000];
int dep[500000],par[500000][19],sub[500000];
ll dis[500000][19];
ll mn[500000];

ll Query(int S,int X[],int T,int Y[]){
	ll ans=inf;
	for(int j=0;j<S;j++){
		int x=X[j];
		for(int i=0;i<=dep[x];i++){
			mn[par[x][i]]=min(mn[par[x][i]],dis[x][i]);
		}
	}
	for(int j=0;j<T;j++){
		int x=Y[j];
		for(int i=0;i<=dep[x];i++){
			ans=min(ans,mn[par[x][i]]+dis[x][i]);
		}
	}
	for(int j=0;j<S;j++){
		int x=X[j];
		for(int i=0;i<=dep[x];i++){
			mn[par[x][i]]=inf;
		}
	}
	return ans;
}

void dfs(int pos,int root){
	sub[pos]=1;
	for(auto x:komsu[pos]){
		if(x.fr==root)continue;
		if(dep[x.fr]!=-1)continue;
		dfs(x.fr,pos);
		sub[pos]+=sub[x.fr];
	}
}

void deco(int pos,int h){
	dfs(pos,pos);
	int total=sub[pos];
	while(true){
		int nex=-1;
		for(auto x:komsu[pos]){
			if(sub[x.fr]>sub[pos])continue;
			if(dep[x.fr]!=-1)continue;
			if(sub[x.fr]>total/2){
				nex=x.fr;
				break;
			}
		}
		if(nex==-1)break;
		pos=nex;
	}
	dep[pos]=h;
	queue<int>q;
	q.push(pos);
	while(q.size()){
		int loc=q.front();
		q.pop();
		par[loc][h]=pos;
		for(auto x:komsu[loc]){
			if(dep[x.fr]!=-1)continue;
			if(dis[x.fr][h]!=0)continue;
			dis[x.fr][h]=dis[loc][h]+x.sc;
			q.push(x.fr);
		}
	}
	for(auto x:komsu[pos]){
		if(dep[x.fr]!=-1)continue;
		deco(x.fr,h+1);
	}
}

void Init(int N,int A[],int B[],int D[]){
	n=N;
	for(int i=0;i<n;i++){
		mn[i]=inf;
	}
	for(int i=0;i<n-1;i++){
		komsu[A[i]].pb({B[i],D[i]});
		komsu[B[i]].pb({A[i],D[i]});
	}
	for(int i=0;i<n;i++){
		dep[i]=-1;
	}
	deco(0,0);
}

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