oj.uz

Submission #50058

# Submission time Handle Problem Language Result Execution time Memory
50058 2018-06-07T07:19:16 Z Diuven Race (IOI11_race) C++11
0 / 100
 6 ms 5332 KB 
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
const int KMX=1000010, MX=200010, inf=2e9;
typedef pair<int, int> pii;

vector<pii> G[MX];
bool done[MX];

int sub[MX];

void init(int v, int par=-1){
	sub[v]=1;
	for(pii &p:G[v]){
		int x=p.first;
		if(done[x] || x==par) continue;
		init(x,v); sub[v]+=sub[x];
	}
}

int findcen(int v, int sz){
	for(pii &p:G[v]){
		int x=p.first;
		if(done[x] || sub[x]>sub[v]) continue;
		if(sub[x]*2>=sz) return findcen(x,sz);
	}
	return v;
}

int dist[KMX];
vector<pii> V, W;
int n, k;

void dfs(int v, int par=-1, int dep=0, int cnt=0){
	for(pii &p:G[v]){
		int x,c; tie(x,c)=p;
		if(x==par || done[x]) continue;
		dfs(x,v,dep+c,cnt+1);
	}
	if(dep<=k){
		V.push_back({dep, cnt});
	}
}

int solve(int v){
	init(v); v=findcen(v, sub[v]); done[v]=true;
	int ans=inf;
	for(pii &p:G[v]){
		int x,c; tie(x,c)=p;
		if(done[x]) continue;
		dfs(x,v,c,1);

		// cutting?
		for(pii &q:V){
			int dep, cnt; tie(dep, cnt)=q;
			ans=min(ans, cnt+dist[k-dep]);
		}
		for(pii &q:V){
			int dep, cnt; tie(dep, cnt)=q;
			dist[dep]=min(dist[dep], cnt);
			W.push_back(q);
		}
		V.clear();
	}
	for(pii &q:W){
		int dep=q.first;
		dist[dep]=inf;
	}
	W.clear();
	for(pii &p:G[v]){
		int x=p.first;
		if(done[x]) continue;
		ans=min(solve(x), ans);
	}
	return ans;
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N, k=K;
	for(int i=0; i<n-1; i++){
		int u=H[i][0], v=H[i][1], c=L[i];
		G[u].push_back({v,c});
		G[v].push_back({u,c});
	}
	fill(dist+1, dist+k+1, inf);
	int ans=solve(0);
	return ans>=inf/2 ? -1 : ans;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 5 ms 5280 KB Output is correct
7 Correct 6 ms 5280 KB Output is correct
8 Correct 5 ms 5280 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Incorrect 5 ms 5332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 5 ms 5280 KB Output is correct
7 Correct 6 ms 5280 KB Output is correct
8 Correct 5 ms 5280 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Incorrect 5 ms 5332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 5 ms 5280 KB Output is correct
7 Correct 6 ms 5280 KB Output is correct
8 Correct 5 ms 5280 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Incorrect 5 ms 5332 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5112 KB Output is correct
2 Correct 6 ms 5212 KB Output is correct
3 Correct 6 ms 5212 KB Output is correct
4 Correct 5 ms 5228 KB Output is correct
5 Correct 5 ms 5228 KB Output is correct
6 Correct 5 ms 5280 KB Output is correct
7 Correct 6 ms 5280 KB Output is correct
8 Correct 5 ms 5280 KB Output is correct
9 Correct 6 ms 5332 KB Output is correct
10 Correct 6 ms 5332 KB Output is correct
11 Incorrect 5 ms 5332 KB Output isn't correct
12 Halted 0 ms 0 KB -