Submission #797761

#	Time	Username	Problem	Language	Result	Execution time	Memory
797761		ttamx	Race (IOI11_race)	C++14	0 / 100	3 ms	5076 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[N];
vector<int> res;

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||cnt>=ans)return;
	res.emplace_back(d);
	dist[d]=min(dist[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])dfs(v,w,1,u);
	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:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  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:26:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |  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:35:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |  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:41:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |  for(auto [v,w]:adj[u])if(!used[v])dfs(v,w,1,u);
      |           ^
race.cpp:44:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   44 |  for(auto [v,w]:adj[u])if(!used[v])decom(v);
      |           ^

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