oj.uz

Submission #160695

# Submission time Handle Problem Language Result Execution time Memory
160695 2019-10-29T10:54:09 Z kig9981 Race (IOI11_race) C++17
0 / 100
 9 ms 8952 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 8952 KB Output isn't correct
2 Halted 0 ms 0 KB -