Submission #797773

#	Time	Username	Problem	Language	Result	Execution time	Memory
797773		ttamx	Race (IOI11_race)	C++14	100 / 100	221 ms	35084 KiB

race

#include "race.h"
#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> p2;

const int N=2e5+5;
const int K=1e6+5;

int n,k;
int ans;
vector<p2> adj[N];
int sz[N];
bool used[N];
int dist[K];
vector<int> res;
vector<p2> res2;

int dfssz(int u,int p=-1){
	sz[u]=1;
	for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=dfssz(v,u);
	return sz[u];
}

int centroid(int u,int cnt,int p=-1){
	for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]*2>cnt)return centroid(v,cnt,u);
	return u;
}

void dfs(int u,int d,int cnt,int p=-1){
	if(d>k)return;
	res.emplace_back(d);
	res2.emplace_back(d,cnt);
	ans=min(ans,cnt+dist[k-d]);
	for(auto [v,w]:adj[u])if(v!=p&&!used[v])dfs(v,d+w,cnt+1,u);
}

void decom(int u){
	u=centroid(u,dfssz(u));
	used[u]=true;
	for(auto [v,w]:adj[u]){
		if(used[v])continue;
		dfs(v,w,1,u);
		for(auto [x,y]:res2)dist[x]=min(dist[x],y);
		res2.clear();
	}
	for(auto i:res)dist[i]=n;
	res.clear();
	for(auto [v,w]:adj[u])if(!used[v])decom(v);
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N,k=K;
	ans=n;
	for(int i=1;i<=k;i++)dist[i]=n;
	for(int i=0;i<n-1;i++){
		int u=H[i][0],v=H[i][1],w=L[i];
		adj[u].emplace_back(v,w);
		adj[v].emplace_back(u,w);
	}
	decom(0);
	return (ans==n?-1:ans);
}

Compilation message (stderr)

race.cpp: In function 'int dfssz(int, int)':
race.cpp:22:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |  for(auto [v,w]:adj[u])if(v!=p&&!used[v])sz[u]+=dfssz(v,u);
      |           ^
race.cpp: In function 'int centroid(int, int, int)':
race.cpp:27:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |  for(auto [v,w]:adj[u])if(v!=p&&!used[v]&&sz[v]*2>cnt)return centroid(v,cnt,u);
      |           ^
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:36:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |  for(auto [v,w]:adj[u])if(v!=p&&!used[v])dfs(v,d+w,cnt+1,u);
      |           ^
race.cpp: In function 'void decom(int)':
race.cpp:42:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |  for(auto [v,w]:adj[u]){
      |           ^
race.cpp:45:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for(auto [x,y]:res2)dist[x]=min(dist[x],y);
      |            ^
race.cpp:50:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   50 |  for(auto [v,w]:adj[u])if(!used[v])decom(v);
      |           ^

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