oj.uz

Submission #80178

# Submission time Handle Problem Language Result Execution time Memory
80178 2018-10-19T12:05:57 Z farukkastamonuda Race (IOI11_race) C++14
9 / 100
 3000 ms 18600 KB 
#include "race.h"
#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 5216 KB Output is correct
3 Correct 8 ms 5320 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 6 ms 5320 KB Output is correct
6 Correct 6 ms 5320 KB Output is correct
7 Correct 6 ms 5320 KB Output is correct
8 Correct 6 ms 5320 KB Output is correct
9 Correct 6 ms 5320 KB Output is correct
10 Correct 6 ms 5320 KB Output is correct
11 Correct 6 ms 5320 KB Output is correct
12 Correct 6 ms 5320 KB Output is correct
13 Correct 6 ms 5320 KB Output is correct
14 Correct 6 ms 5320 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 6 ms 5332 KB Output is correct
18 Correct 7 ms 5332 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 5216 KB Output is correct
3 Correct 8 ms 5320 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 6 ms 5320 KB Output is correct
6 Correct 6 ms 5320 KB Output is correct
7 Correct 6 ms 5320 KB Output is correct
8 Correct 6 ms 5320 KB Output is correct
9 Correct 6 ms 5320 KB Output is correct
10 Correct 6 ms 5320 KB Output is correct
11 Correct 6 ms 5320 KB Output is correct
12 Correct 6 ms 5320 KB Output is correct
13 Correct 6 ms 5320 KB Output is correct
14 Correct 6 ms 5320 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 6 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct
19 Correct 6 ms 5372 KB Output is correct
20 Correct 8 ms 5372 KB Output is correct
21 Correct 24 ms 5376 KB Output is correct
22 Runtime error 22 ms 14972 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 5216 KB Output is correct
3 Correct 8 ms 5320 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 6 ms 5320 KB Output is correct
6 Correct 6 ms 5320 KB Output is correct
7 Correct 6 ms 5320 KB Output is correct
8 Correct 6 ms 5320 KB Output is correct
9 Correct 6 ms 5320 KB Output is correct
10 Correct 6 ms 5320 KB Output is correct
11 Correct 6 ms 5320 KB Output is correct
12 Correct 6 ms 5320 KB Output is correct
13 Correct 6 ms 5320 KB Output is correct
14 Correct 6 ms 5320 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 6 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct
19 Execution timed out 3103 ms 18600 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 5216 KB Output is correct
3 Correct 8 ms 5320 KB Output is correct
4 Correct 7 ms 5320 KB Output is correct
5 Correct 6 ms 5320 KB Output is correct
6 Correct 6 ms 5320 KB Output is correct
7 Correct 6 ms 5320 KB Output is correct
8 Correct 6 ms 5320 KB Output is correct
9 Correct 6 ms 5320 KB Output is correct
10 Correct 6 ms 5320 KB Output is correct
11 Correct 6 ms 5320 KB Output is correct
12 Correct 6 ms 5320 KB Output is correct
13 Correct 6 ms 5320 KB Output is correct
14 Correct 6 ms 5320 KB Output is correct
15 Correct 6 ms 5332 KB Output is correct
16 Correct 7 ms 5332 KB Output is correct
17 Correct 6 ms 5332 KB Output is correct
18 Correct 7 ms 5332 KB Output is correct
19 Correct 6 ms 5372 KB Output is correct
20 Correct 8 ms 5372 KB Output is correct
21 Correct 24 ms 5376 KB Output is correct
22 Runtime error 22 ms 14972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -