Submission #160701

#	Time	Username	Problem	Language	Result	Execution time	Memory
160701		kig9981	Race (IOI11_race)	C++17	100 / 100	998 ms	29764 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 M, D[1000001], P[1000001], W[200000], dist[200000], parent[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;
	parent[C]=C;
	for(auto[n,w]: adj[C]) if(W[n]>0) {
		if((dist[n]=w)>M) continue;
		parent[n]=C;
		Q.emplace(1,n);
		while(!Q.empty()) {
			auto[v,c]=Q.front();
			Q.pop();
			if(P[M-dist[c]]==C) ret=min(ret,v+D[M-dist[c]]);
			for(auto[n,w]: adj[c]) if(dist[n]>dist[c]+w && dist[c]+w<=M) {
				dist[n]=dist[c]+w;
				parent[n]=c;
				Q.emplace(v+1,n);
			}
		}
		Q.emplace(1,n);
		while(!Q.empty()) {
			auto[v,c]=Q.front();
			Q.pop();
			if(P[dist[c]]!=C) {
				P[dist[c]]=C;
				D[dist[c]]=v;
			}
			else D[dist[c]]=min(D[dist[c]],v);
			for(auto[n,w]: adj[c]) if(dist[n]<0x7fffffff && parent[n]==c) 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));
	M=K;
	N=solve(0);
	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:68:16: warning: unused variable 'w' [-Wunused-variable]
    for(auto[n,w]: adj[c]) if(dist[n]<0x7fffffff && parent[n]==c) Q.emplace(v+1,n);
                ^
race.cpp:72:14: warning: unused variable 'w' [-Wunused-variable]
  for(auto[n,w]: adj[C]) if(W[n]>0) ret=min(ret,solve(n));
              ^

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