oj.uz

Submission #80176

# Submission time Handle Problem Language Result Execution time Memory
80176 2018-10-19T12:04:42 Z farukkastamonuda Race (IOI11_race) C++14
9 / 100
 3000 ms 20264 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000000
#define md 1000000007
#define li 200005
#define mp make_pair
#define pb push_back
using namespace std;
int n,k,vis[li],sub[li],mark[li],ans=inf,G[15][2],T[15];
vector< pair<int,int> > v[li],vec;
vector<int> sil;
int calc(int node,int ata=-1){
	sub[node]=0;
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		if(vis[go]==0 && go!=ata) calc(go,node);
	}
	return ++sub[node];
}
int find(int node,int ata,int sz){
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		if(go!=ata && vis[go]==0 && sub[go]>sz/2){
			return find(go,node,sz);
		}
	}
	return node;
}
void dfs(int node,int ata,int val,int st){
	if(val==k) ans=min(ans,st);
	if(val<k){
		ans=min(ans,mark[k-val]+st);
		vec.pb(mp(val,st));
	}
	for(int i=0;i<(int)v[node].size();i++){
		int go=v[node][i].fi;
		if(go!=ata && vis[go]==0) dfs(go,node,val+v[node][i].se,st+1);
	}
}
void solve(int cur=1){
	//printf("*");
	int cen=find(cur,-1,calc(cur));
	sil.clear();
	for(int i=0;i<(int)v[cen].size();i++){
		int go=v[cen][i].fi;
		if(vis[go]==1) continue;
		vec.clear();
		dfs(go,cen,v[cen][i].se,1);
		for(int j=0;j<(int)vec.size();j++){
			mark[vec[j].fi]=min(mark[vec[j].fi],vec[j].se);
			sil.pb(vec[j].fi);
		}
	}
	for(int i=0;i<(int)sil.size();i++){
		mark[sil[i]]=inf;
	}
	vis[cen]=1;
	//sil.clear();
	for(int i=0;i<(int)v[cen].size();i++){
		int git=v[cen][i].fi;
		if(vis[git]==0) solve(git);
	}
}
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]+1;
		int vv=H[i][1]+1;
		int c=L[i];
		v[u].pb(mp(vv,c));
		v[vv].pb(mp(u,c));
	}
	for(int i=0;i<=k;i++) mark[i]=inf;
	solve();
	if(ans>=inf) ans=-1;
	return ans;
}
//~ int main(){
	//~ G[0][0]=0,G[0][1]=1;
	//~ G[1][0]=1,G[1][1]=2;
	//~ G[2][0]=1,G[2][1]=3;
	//~ T[0]=1,T[1]=2,T[2]=4;
	//~ int ty=best_path(4,3,G,T);
	//~ printf("%d\n",ty);
	//~ return 0;
//}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5236 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 10 ms 5292 KB Output is correct
8 Correct 6 ms 5344 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 6 ms 5356 KB Output is correct
11 Correct 6 ms 5384 KB Output is correct
12 Correct 6 ms 5384 KB Output is correct
13 Correct 8 ms 5384 KB Output is correct
14 Correct 6 ms 5384 KB Output is correct
15 Correct 6 ms 5384 KB Output is correct
16 Correct 6 ms 5384 KB Output is correct
17 Correct 6 ms 5412 KB Output is correct
18 Correct 6 ms 5416 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5236 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 10 ms 5292 KB Output is correct
8 Correct 6 ms 5344 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 6 ms 5356 KB Output is correct
11 Correct 6 ms 5384 KB Output is correct
12 Correct 6 ms 5384 KB Output is correct
13 Correct 8 ms 5384 KB Output is correct
14 Correct 6 ms 5384 KB Output is correct
15 Correct 6 ms 5384 KB Output is correct
16 Correct 6 ms 5384 KB Output is correct
17 Correct 6 ms 5412 KB Output is correct
18 Correct 6 ms 5416 KB Output is correct
19 Correct 7 ms 5464 KB Output is correct
20 Correct 6 ms 5468 KB Output is correct
21 Correct 24 ms 5728 KB Output is correct
22 Runtime error 18 ms 15272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5236 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 10 ms 5292 KB Output is correct
8 Correct 6 ms 5344 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 6 ms 5356 KB Output is correct
11 Correct 6 ms 5384 KB Output is correct
12 Correct 6 ms 5384 KB Output is correct
13 Correct 8 ms 5384 KB Output is correct
14 Correct 6 ms 5384 KB Output is correct
15 Correct 6 ms 5384 KB Output is correct
16 Correct 6 ms 5384 KB Output is correct
17 Correct 6 ms 5412 KB Output is correct
18 Correct 6 ms 5416 KB Output is correct
19 Execution timed out 3036 ms 20264 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 6 ms 5116 KB Output is correct
3 Correct 6 ms 5184 KB Output is correct
4 Correct 6 ms 5184 KB Output is correct
5 Correct 7 ms 5236 KB Output is correct
6 Correct 6 ms 5244 KB Output is correct
7 Correct 10 ms 5292 KB Output is correct
8 Correct 6 ms 5344 KB Output is correct
9 Correct 6 ms 5356 KB Output is correct
10 Correct 6 ms 5356 KB Output is correct
11 Correct 6 ms 5384 KB Output is correct
12 Correct 6 ms 5384 KB Output is correct
13 Correct 8 ms 5384 KB Output is correct
14 Correct 6 ms 5384 KB Output is correct
15 Correct 6 ms 5384 KB Output is correct
16 Correct 6 ms 5384 KB Output is correct
17 Correct 6 ms 5412 KB Output is correct
18 Correct 6 ms 5416 KB Output is correct
19 Correct 7 ms 5464 KB Output is correct
20 Correct 6 ms 5468 KB Output is correct
21 Correct 24 ms 5728 KB Output is correct
22 Runtime error 18 ms 15272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -