Submission #234522

#	Time	Username	Problem	Language	Result	Execution time	Memory
234522		kshitij_sodani	Factories (JOI14_factories)	C++17	0 / 100	29 ms	24448 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[22][500001];
llo par[500001];
llo rr=0;
llo mi[500001];
llo ma[500001];
llo dist[500001][25];


llo cur;
void dfs(llo no,llo parr=-1){
	ss[cur][no]=1;
	for(auto j:adj[no]){
		if(j.a==parr){
			continue;
		}
		dfs(j.a,no);
		ss[cur][no]+=ss[cur][j.a];
	}	
}
void dfs2(llo no,llo parr=-1,llo lev=0){
/*	if(dist[cur][no]!=-1){
	//if(parr!=-1 and lev==0){
		while(true){
			continue;
		}
	}*/
	dist[cur][no]=lev;
//	cout<<cur<<".."<<no<<".."<<lev<<endl;
	for(auto j:adj[no]){
		if(j.a==parr){
			continue;
		}
		dfs2(j.a,no,lev+j.b);
	}	
}
llo find(llo no,llo par4=-1){
	llo st=0;
//	cout<<no<<":";
	for(auto j:adj[no]){
		if(j.a==par4){
			continue;
		}
		if(ss[cur][j.a]>ss[cur][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);
	//llo cen=no;
	dfs2(cen);
	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++){
		for(llo j=0;j<21;j++){
			dist[i][j]=-1;
		}
	}
	for(llo i=0;i<n;i++){
		ma[i]=-1;
		mi[i]=-1;
	}
	for(llo i=0;i<n-1;i++){
		adj[(llo)aa[i]].insert({(llo)bb[i],(llo)dd[i]});
		adj[(llo)bb[i]].insert({(llo)aa[i],(llo)dd[i]});
	}
	dec(0);
	/*for(llo i=0;i<n;i++){
		cout<<par[i]<<","<<ww[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=(llo)x[i];
		llo count=0;
		while(no!=-1){
			no=par[no];
			count+=1;
		}
		no=(llo)x[i];
		llo pc=0;
		while(no!=-1){
			if(mi[no]==-1){
				mi[no]=dist[count-pc-1][(llo)x[i]];

			}
			else{
				mi[no]=min(mi[no],dist[count-pc-1][(llo)x[i]]);
			}
		/*	if(x[i]!=no and dist[count-pc-1][(llo)x[i]]==0){
					while(true){
						continue;
					}
				}*/
			rem.pb(no);
			no=par[no];
			pc+=1;
		}
	}
	for(llo i=0;i<(llo)t;i++){
		llo no=(llo)y[i];
		llo count=0;
		while(no!=-1){
			no=par[no];
			count+=1;
		}
		no=(llo)y[i];
		llo pc=0;
		while(no!=-1){
			if(ma[no]==-1){
				ma[no]=dist[count-pc-1][(llo)y[i]];

			}
			else{
				ma[no]=min(ma[no],dist[count-pc-1][(llo)y[i]]);
			}
		/*	if(y[i]!=no and dist[count-pc-1][(llo)y[i]]==0){
					while(true){
						continue;
					}
				}*/
			rem.pb(no);
			if(mi[no]!=-1 and ma[no]!=-1){
				if(ans==-1){
					ans=mi[no]+ma[no];
				}
				else{
					ans=min(ans,mi[no]+ma[no]);
				}
			}
			no=par[no];
			pc+=1;
		}
	}
	/*for(int i=0;i<5001;i++){
		mi[i]=-1;
		ma[i]=-1;
	}*/
	for(auto j:rem){
		ma[j]=-1;
		mi[j]=-1;
	}
	/*for(llo i=0;i<(llo)s;i++){
		llo no=(llo)x[i];
		llo tot=0;
		while(no!=-1){
			mi[no]=-1;
			no=par[no];
		}
	}
	for(llo i=0;i<(llo)t;i++){
		llo no=(llo)y[i];
		llo tot=0;
		while(no!=-1){
			ma[no]=-1;
			no=par[no];
		}
	}*/
/*	if(ans==0){
		while(true){
			continue;
		}
	}*/
	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)<<endl;
	}
	return 0;
}*/

Compilation message (stderr)

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

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