Submission #234495

#	Time	Username	Problem	Language	Result	Execution time	Memory
234495		kshitij_sodani	Factories (JOI14_factories)	C++17	0 / 100	30 ms	24444 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 ww[500001];
llo par[500001];
llo rr=0;
llo mi[500001];
llo ma[500001];


llo 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];
	}	
}
pair<llo,llo> find(llo no,llo par=-1,llo wow=0){
	llo st=0;
	//cout<<no<<",";
	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		if(ss[j.a]>ss[rr]/2){
			return find(j.a,no,wow+j.b);
		}
	}
	if(st==0){
		return {no,wow};
	}
}
llo dec(llo no,llo parc=-1,llo www=0){
	rr=no;
	dfs(no);

	
	pair<llo,llo> kk=find(no);
	//cout<<endl;
	ww[kk.a]=kk.b+www;
	if(parc==-1){
		ww[kk.a]=0;
	}
	llo cen=kk.a;
	for(auto j:adj[cen]){
		adj[j.a].erase({cen,j.b});
	}
	par[cen]=parc;
	for(auto j:adj[cen]){
		dec(j.a,cen,j.b);
	}
}
void Init(int n,int aa[],int bb[],int dd[]){
	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;
	for(llo i=0;i<(llo)s;i++){
		llo no=(llo)x[i];
		llo tot=0;
		while(no!=-1){
			if(mi[no]==-1){
				mi[no]=tot;
			}
			else{
				mi[no]=min(mi[no],tot);
			}
			tot+=ww[no];
			no=par[no];
		}
	}
	for(llo i=0;i<(llo)t;i++){
		llo no=(llo)y[i];
		llo tot=0;
		while(no!=-1){
			if(ma[no]==-1){
				ma[no]=tot;
			}
			else{
				ma[no]=min(ma[no],tot);
			}
			if(mi[no]!=-1){
				if(ans==-1){
					ans=mi[no]+ma[no];
				}
				else{
					ans=min(ans,mi[no]+ma[no]);
				}
			}
			tot+=ww[no];
			no=par[no];
		}
	}
	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];
		}
	}

	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;
}*/

Compilation message (stderr)

factories.cpp: In function 'llo dfs(llo, llo)':
factories.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
factories.cpp: In function 'llo dec(llo, llo, llo)':
factories.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
factories.cpp: In function 'llo Query(int, int*, int, int*)':
factories.cpp:118:7: warning: unused variable 'tot' [-Wunused-variable]
   llo tot=0;
       ^~~
factories.cpp:126:7: warning: unused variable 'tot' [-Wunused-variable]
   llo tot=0;
       ^~~
factories.cpp: In function 'std::pair<long long int, long long int> find(llo, llo, llo)':
factories.cpp:42:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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