제출 #234536

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234536		kshitij_sodani	공장들 (JOI14_factories)	C++17	100 / 100	6729 ms	222324 KiB

factories

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "factories.h"
set<pair<llo,llo>> adj[500001];
llo ss[500001];
llo par[500001];
llo rr=0;
llo mi[500001];
//llo ma[500001];
llo dist[22][500001];
//llo vis[500001];
llo lol[500001];
llo cur;
void dfs(llo no,llo parr=-1){
	ss[no]=1;
	for(auto j:adj[no]){
		if(j.a==parr){
			continue;
		}
		dfs(j.a,no);
		ss[no]+=ss[j.a];
	}	
}
void dfs2(llo no,llo parr=-1,llo lev=0,llo cur2=0){
	dist[cur2][no]=lev;
//	cout<<cur2<<".."<<no<<".."<<lev<<endl;
	for(auto j:adj[no]){
		if(j.a==parr){
			continue;
		}
		dfs2(j.a,no,lev+j.b,cur2);
	}	
}
llo find(llo no,llo par4=-1){
	llo st=0;
//	cout<<no<<":";
	for(auto j:adj[no]){
		if(j.a==par4){
			continue;
		}
		if(ss[j.a]>ss[rr]/2){
			st=1;
			return find(j.a,no);
		}
	}
	if(st==0){
		return no;
	}
}
 
void dec(llo no,llo parc=-1,llo pop=0){
	rr=no;
	cur=pop;
	dfs(no);
	llo cen=find(no);
	lol[cen]=pop;
	//llo cen=no;
	dfs2(cen,-1,0,pop);
	for(auto j:adj[cen]){
		adj[j.a].erase({cen,j.b});
	}
	par[cen]=parc;
	for(auto j:adj[cen]){
		dec(j.a,cen,pop+1);
	}
}
void Init(int nn,int aa[],int bb[],int dd[]){
	llo n=(llo)nn;
//	for(llo i=0;i<n;i++){
	//	vis[i]=0;
/*		for(llo j=0;j<21;j++){
			dist[j][i]=-1;
		}*/
//	}
	for(llo i=0;i<n;i++){
	//	ma[i]=-1;
		mi[i]=-1;
	}
	for(llo i=0;i<n-1;i++){
		adj[aa[i]].insert({(llo)bb[i],(llo)dd[i]});
		adj[bb[i]].insert({(llo)aa[i],(llo)dd[i]});
	}
	dec(0);
	/*for(llo i=0;i<n;i++){
		cout<<par[i]<<":"<<endl;
	}*/
}	
 
llo Query(int s,int x[],int t,int y[]){
	llo ans=-1;
	vector<llo> rem;
	for(llo i=0;i<(llo)s;i++){
		llo no;
		no=(llo)x[i];
		llo pc=0;
		while(no!=-1){
			if(mi[no]==-1){
				mi[no]=dist[lol[x[i]]-pc][(llo)x[i]];
 
			}
			else{
				mi[no]=min(mi[no],dist[lol[x[i]]-pc][(llo)x[i]]);
			}
			rem.pb(no);
			no=par[no];
			pc+=1;
		}
	}
	for(llo i=0;i<(llo)t;i++){
		llo no;
		
		no=(llo)y[i];
		llo pc=0;
		while(no!=-1){
			if(mi[no]!=-1 ){
				if(ans==-1){
					ans=mi[no]+dist[lol[y[i]]-pc][(llo)y[i]];
				}
				else{
					ans=min(ans,mi[no]+dist[lol[y[i]]-pc][(llo)y[i]]);
				}
			}
			no=par[no];
			pc+=1;
		}
	}

	for(auto j:rem){
	//	ma[j]=-1;
		mi[j]=-1;
	}

	return ans;
 
}
/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,q;
	cin>>n>>q;
	int aa[n];
	int bb[n];
	int dd[n];
	for(llo i=0;i<n-1;i++){
		cin>>aa[i]>>bb[i]>>dd[i];
	}
	Init(n,aa,bb,dd);
	for(int i=0;i<q;i++){
		int s,t;
		cin>>s>>t;
		int ac[s];
		int bc[t];
		for(int j=0;j<s;j++){
			cin>>ac[j];
		}
		for(int j=0;j<t;j++){
			cin>>bc[j];
		}
		cout<<Query(s,ac,t,bc)<<'\n';
	}
	return 0;
}*/

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'llo find(llo, llo)':
factories.cpp:54:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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