oj.uz

Submission #160700

# Submission time Handle Problem Language Result Execution time Memory
160700 2019-10-29T11:16:31 Z kig9981 Race (IOI11_race) C++17
0 / 100
 3000 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 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;
	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(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

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:67:16: warning: unused variable 'w' [-Wunused-variable]
    for(auto[n,w]: adj[c]) if(parent[n]==c) Q.emplace(v+1,n);
                ^
race.cpp:71: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 Execution timed out 3017 ms 8952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3017 ms 8952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3017 ms 8952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3017 ms 8952 KB Time limit exceeded
2 Halted 0 ms 0 KB -