Submission #576257

#	Time	Username	Problem	Language	Result	Execution time	Memory
576257		itnes	Race (IOI11_race)	C++14	100 / 100	730 ms	50320 KiB

race

#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef pair<int,int> pii;
const ll INFLL=1e18+7;
const int INF=1e9+7;
#define pb push_back
const int MAXN=2e5+7,MAXM=1e6+7;
int n,k;
list<pii> G[MAXN];
pair<list<pii>::iterator,list<pii>::iterator> edges[MAXN];
int cost[MAXN];
int res=INF;
int amount[MAXN],depth[MAXN];
void set_dp(int x,int pre){
	depth[x]=depth[pre]+1;
	for(pii v:G[x]) if(v.first!=pre) set_dp(v.first,x);
	amount[x]=1;
	for(pii v:G[x]) if(v.first!=pre) amount[x]+=amount[v.first];
}
int centroid(int x,int pre,int N){
	int maxi=0,pos=0;
	for(pii v:G[x]){
		if(v.first!=pre){
			if(amount[v.first]>maxi){
				maxi=amount[v.first];
				pos=v.first;
			}
		}
	}
	if(maxi<=N/2) return x;
	return centroid(pos,x,N);
}
vector<int> to_reverse,to_temp;
int dist[MAXN];
int best[MAXM];
int temp[MAXM];
void prepare(int x,int pre){
	if(dist[x]>k) return;
	depth[x]=depth[pre]+1;
	to_reverse.pb(dist[x]);
	to_temp.pb(dist[x]);
	temp[dist[x]]=min(temp[dist[x]],depth[x]);
	res=min(res,temp[dist[x]]+best[k-dist[x]]);
	//~ cout<<dist[x]<<" & "<<k-dist[x]<<" | ";
	//~ cout<<temp[dist[x]]<<" + "<<best[k-dist[x]]<<"\n";
	for(pii v:G[x]){
		if(v.first!=pre){
			dist[v.first]=dist[x]+cost[v.second];
			if(dist[v.first]>k) continue;
			prepare(v.first,x);
		}
	}
}
void clean(int x,int pre){
	dist[x]=depth[x]=0;
	for(pii v:G[x]) if(v.first!=pre) clean(v.first,x);
}
void decompose(int x,int pre){
	set_dp(x,pre);
	int vert=centroid(x,x,amount[x]);
	//actual calculations
	depth[vert]=0;
	for(pii v:G[vert]){
		dist[v.first]=cost[v.second];
		prepare(v.first,vert);
		for(int w:to_temp) best[w]=min(best[w],temp[w]);
		for(int w:to_temp) temp[w]=INF;
		to_temp.clear();
	}
	for(int v:to_reverse) best[v]=INF;
	to_reverse.clear();
	clean(vert,vert);
	vector<pii> neigs;
	for(pii v:G[vert]) neigs.pb(v);
	for(pii v:neigs){
		if(x>v.first) swap(edges[v.second].first,edges[v.second].second);
		G[x].erase(edges[v.second].first);
		G[v.first].erase(edges[v.second].second); 
	}
	for(pii v:neigs) decompose(v.first,vert);
}
int best_path(int N,int K,int H[][2],int* L){
	n=N; k=K;
	for(int i=0;i<n-1;++i){
		if(H[i][0]>H[i][1]) swap(H[i][0],H[i][1]);
		G[H[i][0]].push_front({H[i][1],i});
		G[H[i][1]].push_front({H[i][0],i});
		edges[i]={G[H[i][0]].begin(),G[H[i][1]].begin()};
	}
	for(int i=0;i<n-1;++i) cost[i]=L[i];
	for(int i=1;i<MAXM;++i) best[i]=temp[i]=INF;
	decompose(0,0);
	return (res==INF?-1:res);
}
//~ int main()
//~ {
	//~ ios_base::sync_with_stdio(0);
	//~ int arr[10][2]={{0,1},{0,2},{2,3},{3,4},{4,5},{0,6},{6,7},{6,8},{8,9},{8,10}};
	//~ int arr2[10]={3,4,5,4,6,3,2,5,6,7};
	//~ cout<<best_path(11,12,arr,arr2)<<"\n";
//~ }

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