Submission #399075

#	Time	Username	Problem	Language	Result	Execution time	Memory
399075		Petremol	Race (IOI11_race)	C++17	21 / 100	228 ms	14276 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define int long long int
#define all(x) x.begin(), x.end()
#define send ios_base::sync_with_stdio(false);
#define help cin.tie(NULL)
#define inf (int)(1e17+1)
#define mod (int)(1e9+7)
#define N (int)(2e5+5)
#define fi first
#define se second
#define endl "\n"
#define double long double
#define eps (double)(1e-9)
#define sa cout<<"sa"<<endl
using namespace std;

int n,k;
vector <pair<int,int>> adj[N];
vector <int> sz(N);
vector <bool> mrk(N);

int sdfs(int c,int pre=0){
	sz[c]=1;
	for(auto x:adj[c]){
		if(x.fi==pre||mrk[x.fi]) continue;
		sz[c]+=sdfs(x.fi,c);
	}
	return sz[c];
}

int get(int c,int pre,int s){
	for(auto x:adj[c]){
		if(x.fi==pre||mrk[x.fi]) continue;
		if(2*sz[x.fi]>s) return get(x.fi,c,s);
	}
	return c;
}

map <int,int> cmp;

void dfs(int c,int pre,int d,int cur){
	if(cur>k) return;
	for(auto x:adj[c]){
		if(x.fi==pre||mrk[x.fi]) continue;
		dfs(x.fi,c,d+1,cur+x.se);
	}
	cmp[cur]=d;
}

int ans=inf;

void centroid(int c){
	c=get(c,0,sdfs(c));
	mrk[c]=1;

	map<int,int> mp;
	mp[0]=0;

	for(auto x:adj[c]) if(!mrk[x.fi]){
		dfs(x.fi,c,1,x.se);
		if(mp.size()<cmp.size()) swap(mp,cmp);
		for(auto e:cmp) if(mp.count(k-e.fi)) ans=min(ans,e.se+mp[k-e.fi]);
		for(auto e:cmp){
			if(mp.count(e.fi)) mp[e.fi]=min(mp[e.fi],e.se);
			else mp[e.fi]=e.se;
		}
		cmp.clear();
	}

	for(auto x:adj[c]) if(!mrk[x.fi]) centroid(x.fi);
}

int32_t best_path(int32_t Na, int32_t Ka, int32_t H[][2], int32_t L[]){
	n=Na;k=Ka;
	for(int i=0;i<n-1;i++){
		int u=H[i][0],v=H[i][1],w=L[i];
		++u;++v;
		adj[u].push_back({v,w});
		adj[v].push_back({u,w});
	}
	centroid(1);
	return((ans!=inf)?ans:-1);
}

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