Submission #234675

#	Time	Username	Problem	Language	Result	Execution time	Memory
234675		kshitij_sodani	Race (IOI11_race)	C++17	100 / 100	751 ms	63316 KiB

race

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#include "race.h"
#define a first 
#define pb push_back
#define b second
pair<int,int> aa[1000001];
pair<int,int> bb[1000001];
int ss[200001];
set<pair<int,int>> adj[200001];
int cur;
vector<int> del;
int k;
int ans=-1;
void dfs(int no,int par=-1){
	ss[no]=1;
	for(auto j:adj[no]){
		if(j.a!=par){
			dfs(j.a,no);
			ss[no]+=ss[j.a];
		}
	}
}
int dfs2(int no,int par=-1){
	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		if(ss[j.a]>ss[cur]/2){
			return dfs2(j.a,no);
		}
	}
	return no;
}
void dfs3(int no,int par2,int par=-1,int lev=0,int ww=0){
	if(lev==1){
		par2=no;
	}
	if(ww<=k){

		del.pb(ww);
		if(aa[ww].a==-1){
			aa[ww]={par2,lev};
		}
		else if(aa[ww].a==par2){
			aa[ww].b=min(aa[ww].b,lev);
		}
		else if(aa[ww].b>lev){
			bb[ww]=aa[ww];
			aa[ww]={par2,lev};
		}
		else if(bb[ww].a==-1){
			bb[ww]={par2,lev};
		}
		else if(bb[ww].a==par2){
			bb[ww].b=min(bb[ww].b,lev);
		}
		else if(lev<bb[ww].b){
			bb[ww]={par2,lev};
		}
		if(aa[ww].a!=-1 and aa[k-ww].a!=-1){
			if(aa[ww].a!=aa[k-ww].a){
				if(ans==-1){
					ans=aa[ww].b+aa[k-ww].b;
				}
				ans=min(ans,aa[ww].b+aa[k-ww].b);
			}
		}
		if(aa[ww].a!=-1 and bb[k-ww].a!=-1){
			if(aa[ww].a!=bb[k-ww].a){
				if(ans==-1){
					ans=aa[ww].b+bb[k-ww].b;
				}
				ans=min(ans,aa[ww].b+bb[k-ww].b);
			}
		}
		if(bb[ww].a!=-1 and aa[k-ww].a!=-1){
			if(bb[ww].a!=aa[k-ww].a){
				if(ans==-1){
					ans=bb[ww].b+aa[k-ww].b;
				}
				ans=min(ans,bb[ww].b+aa[k-ww].b);
			}
		}
		if(bb[ww].a!=-1 and bb[k-ww].a!=-1){
			if(bb[ww].a!=bb[k-ww].a){
				if(ans==-1){
					ans=bb[ww].b+bb[k-ww].b;
				}
				ans=min(ans,bb[ww].b+bb[k-ww].b);
			}
		}
	}

	for(auto j:adj[no]){
		if(j.a==par){
			continue;
		}
		dfs3(j.a,par2,no,lev+1,ww+j.b);

	}
}
void dec(int no){
	cur=no;
	dfs(no);
	//return;
	int cen=dfs2(no);

	dfs3(cen,cen);
	for(auto j:del){
		aa[j]={-1,-1};
		bb[j]={-1,-1};
	}
	del.clear();
	for(auto j:adj[cen]){
		adj[j.a].erase({cen,j.b});
	}
	for(auto j:adj[cen]){
		dec(j.a);
	}
	return;
}

int best_path(int n,int kk,int h[][2],int l[]){
	k=kk;
	for(int i=0;i<=k;i++){
		aa[i]={-1,-1};
		bb[i]={-1,-1};
	}
	for(int i=0;i<n-1;i++){
		adj[h[i][0]].insert({h[i][1],l[i]});
		adj[h[i][1]].insert({h[i][0],l[i]});
	}
	dec(0);
	return ans;
}

/*int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,ko;
	cin>>n>>ko;
	int hh[n-1][2];
	int lol[n-1];
	for(int i=0;i<n-1;i++){
		cin>>hh[i][0]>>hh[i][1]>>lol[i];
	}
	cout<<best_path(n,ko,hh,lol)<<endl;
	return 0;
}
*/

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57