Submission #160695

#	Time	Username	Problem	Language	Result	Execution time	Memory
160695		kig9981	Race (IOI11_race)	C++17	0 / 100	9 ms	8952 KiB

race

#include "race.h"
#include <bits/stdc++.h>
 
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
 
using namespace std;

vector<pair<int,int>> adj[200000];
int K, D[1000001], P[1000001], W[200000], dist[200000];

void reset(int c)
{
	W[c]=0;
	for(auto[n,w]: adj[c]) if(W[n]>0) reset(n);
}

int dfs(int c)
{
	W[c]=1; dist[c]=0x7fffffff;
	for(auto[n,w]: adj[c]) if(W[n]==0) W[c]+=dfs(n);
	return W[c];
}

int centroid(int c, int v)
{
	for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>v) return centroid(n,v);
	return c;
}

int solve(int c)
{
	int ret=0x7fffffff;
	queue<pair<int,int>> Q;
	reset(c);
	dist[c=centroid(c,dfs(c))]=0;
	D[0]=0;
	P[0]=c;
	for(auto[n,w]: adj[c]) {
		dist[n]=w;
		if(dist[n]>K) continue;
		if(P[dist[n]]!=c) {
			P[dist[n]]=c;
			D[dist[n]]=1;
		}
		else D[dist[n]]=min(D[dist[n]],1);
		if(P[K-dist[n]]==c) ret=min(ret,D[dist[n]]+D[K-dist[n]]);
		Q.emplace(1,n);
		while(!Q.empty()) {
			auto[v,c]=Q.front();
			Q.pop();
			for(auto[n,w]: adj[c]) if(dist[n]>dist[c]+w && dist[c]+w<=K) {
				dist[n]=dist[c]+w;
				if(P[dist[n]]!=c) {
					P[dist[n]]=c;
					D[dist[n]]=v+1;
				}
				else D[dist[n]]=min(D[dist[n]],v+1);
				if(P[K-dist[n]]==c) ret=min(ret,D[dist[n]]+D[K-dist[n]]);
				Q.emplace(v+1,n);
			}
		}
	}
	W[c]=-1;
	for(auto[n,w]: adj[c]) if(W[n]>0) ret=min(ret,solve(n));
	return ret;
}

int best_path(int N, int K, int H[][2], int L[])
{
	for(int i=0;i<N-1;i++) {
		adj[H[i][0]].emplace_back(H[i][1],L[i]);
		adj[H[i][1]].emplace_back(H[i][0],L[i]);
	}
	memset(P,-1,sizeof(P));
	N=solve(0); ::K=K;
	return N==0x7fffffff ? -1:N;
}

Compilation message (stderr)

race.cpp: In function 'void reset(int)':
race.cpp:20:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(W[n]>0) reset(n);
              ^
race.cpp: In function 'int dfs(int)':
race.cpp:26:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(W[n]==0) W[c]+=dfs(n);
              ^
race.cpp: In function 'int centroid(int, int)':
race.cpp:32:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(W[n]<W[c] && 2*W[n]>v) return centroid(n,v);
              ^
race.cpp: In function 'int solve(int)':
race.cpp:70:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[c]) if(W[n]>0) ret=min(ret,solve(n));
              ^

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