답안 #94653 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94653	2019-01-22T06:45:16 Z	andy627	경주 (Race) (IOI11_race)	C++17	100 / 100	1273 ms	38760 KB

race

#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#define pii pair<int,int>
#define ff first
#define ss second
#define INF 1e9
using namespace std;

int n,k;
vector<pii> edge[222222];
int siz[222222];

set<int> st;
vector<pii> vc;
int cnt[1111111];
bool is_cent[222222];

int ans=INF;

int dfs_siz(int v,int p){
	siz[v]=1;
	for(pii u:edge[v]){
		if(u.ff==p || is_cent[u.ff]) continue;
		siz[v]+=dfs_siz(u.ff,v);
	}
	return siz[v];
}

int cent(int rt){
	int v=rt,p=rt;
	
	while(1){
		int mx=-1,mxi;
		for(pii u:edge[v]){
			if(u.ff==p || is_cent[u.ff]) continue;
			if(mx<siz[u.ff]){
				mx=siz[u.ff];
				mxi=u.ff;
			}
		}
		if(mx==-1 || mx<=siz[rt]/2) break;
		p=v; v=mxi;
	}
	return v;
}

void dfs_dist(int v,int p,int dist1,int dist2){
	vc.push_back({dist1,dist2});

	for(pii u:edge[v]){
		if(u.ff==p || is_cent[u.ff]) continue;
		if(dist1+u.ss<=k) dfs_dist(u.ff,v,dist1+u.ss,dist2+1);
	}
}

void cent_dnc(int v){
	dfs_siz(v,v);
	v=cent(v); is_cent[v]=1;

	//printf("%d\n",v);

	st.clear();
	st.insert(0); cnt[0]=0;
	for(pii u:edge[v]){
		if(is_cent[u.ff] || u.ss>k) continue;

		vc.clear();
		dfs_dist(u.ff,v,u.ss,1);

		//for(pii dist:vc) printf("%d %d\n",dist.ff,dist.ss);

		for(pii dist:vc){
			if(st.find(k-dist.ff)!=st.end()) ans=min(ans,cnt[k-dist.ff]+dist.ss);
		}

		for(pii dist:vc){
			if(st.find(dist.ff)==st.end()){
				st.insert(dist.ff);
				cnt[dist.ff]=dist.ss;
			}
			else cnt[dist.ff]=min(cnt[dist.ff],dist.ss);
		}

		//printf("%d\n\n",ans);
	}

	for(pii u:edge[v]){
		if(is_cent[u.ff]) continue;
		cent_dnc(u.ff);
	}
}

int best_path(int N, int K, int H[][2], int L[]){
	n=N; k=K;

	for(int i=0;i<n-1;i++){
		edge[H[i][0]].push_back({H[i][1],L[i]});
		edge[H[i][1]].push_back({H[i][0],L[i]});
	}

	cent_dnc(0);

	if(ans==INF) return -1;
	return ans;
}

Subtask #1
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5496 KB	Output is correct
2	Correct	6 ms	5624 KB	Output is correct
3	Correct	5 ms	5596 KB	Output is correct
4	Correct	5 ms	5596 KB	Output is correct
5	Correct	6 ms	5624 KB	Output is correct
6	Correct	5 ms	5624 KB	Output is correct
7	Correct	4 ms	5624 KB	Output is correct
8	Correct	5 ms	5624 KB	Output is correct
9	Correct	5 ms	5624 KB	Output is correct
10	Correct	5 ms	5496 KB	Output is correct
11	Correct	5 ms	5496 KB	Output is correct
12	Correct	5 ms	5624 KB	Output is correct
13	Correct	5 ms	5496 KB	Output is correct
14	Correct	5 ms	5624 KB	Output is correct
15	Correct	5 ms	5624 KB	Output is correct
16	Correct	5 ms	5624 KB	Output is correct
17	Correct	6 ms	5624 KB	Output is correct
18	Correct	5 ms	5624 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5496 KB	Output is correct
2	Correct	6 ms	5624 KB	Output is correct
3	Correct	5 ms	5596 KB	Output is correct
4	Correct	5 ms	5596 KB	Output is correct
5	Correct	6 ms	5624 KB	Output is correct
6	Correct	5 ms	5624 KB	Output is correct
7	Correct	4 ms	5624 KB	Output is correct
8	Correct	5 ms	5624 KB	Output is correct
9	Correct	5 ms	5624 KB	Output is correct
10	Correct	5 ms	5496 KB	Output is correct
11	Correct	5 ms	5496 KB	Output is correct
12	Correct	5 ms	5624 KB	Output is correct
13	Correct	5 ms	5496 KB	Output is correct
14	Correct	5 ms	5624 KB	Output is correct
15	Correct	5 ms	5624 KB	Output is correct
16	Correct	5 ms	5624 KB	Output is correct
17	Correct	6 ms	5624 KB	Output is correct
18	Correct	5 ms	5624 KB	Output is correct
19	Correct	6 ms	5624 KB	Output is correct
20	Correct	6 ms	5496 KB	Output is correct
21	Correct	7 ms	5624 KB	Output is correct
22	Correct	8 ms	8056 KB	Output is correct
23	Correct	8 ms	7800 KB	Output is correct
24	Correct	9 ms	8440 KB	Output is correct
25	Correct	9 ms	7416 KB	Output is correct
26	Correct	8 ms	6904 KB	Output is correct
27	Correct	6 ms	5624 KB	Output is correct
28	Correct	8 ms	6392 KB	Output is correct
29	Correct	8 ms	6904 KB	Output is correct
30	Correct	8 ms	7032 KB	Output is correct
31	Correct	9 ms	7420 KB	Output is correct
32	Correct	9 ms	7544 KB	Output is correct
33	Correct	10 ms	8312 KB	Output is correct
34	Correct	9 ms	7928 KB	Output is correct
35	Correct	9 ms	8572 KB	Output is correct
36	Correct	9 ms	8952 KB	Output is correct
37	Correct	9 ms	7544 KB	Output is correct
38	Correct	8 ms	6776 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5496 KB	Output is correct
2	Correct	6 ms	5624 KB	Output is correct
3	Correct	5 ms	5596 KB	Output is correct
4	Correct	5 ms	5596 KB	Output is correct
5	Correct	6 ms	5624 KB	Output is correct
6	Correct	5 ms	5624 KB	Output is correct
7	Correct	4 ms	5624 KB	Output is correct
8	Correct	5 ms	5624 KB	Output is correct
9	Correct	5 ms	5624 KB	Output is correct
10	Correct	5 ms	5496 KB	Output is correct
11	Correct	5 ms	5496 KB	Output is correct
12	Correct	5 ms	5624 KB	Output is correct
13	Correct	5 ms	5496 KB	Output is correct
14	Correct	5 ms	5624 KB	Output is correct
15	Correct	5 ms	5624 KB	Output is correct
16	Correct	5 ms	5624 KB	Output is correct
17	Correct	6 ms	5624 KB	Output is correct
18	Correct	5 ms	5624 KB	Output is correct
19	Correct	204 ms	12252 KB	Output is correct
20	Correct	201 ms	12280 KB	Output is correct
21	Correct	206 ms	12528 KB	Output is correct
22	Correct	186 ms	12724 KB	Output is correct
23	Correct	122 ms	12740 KB	Output is correct
24	Correct	95 ms	12464 KB	Output is correct
25	Correct	210 ms	14208 KB	Output is correct
26	Correct	101 ms	16940 KB	Output is correct
27	Correct	277 ms	19372 KB	Output is correct
28	Correct	506 ms	27512 KB	Output is correct
29	Correct	455 ms	26836 KB	Output is correct
30	Correct	275 ms	19320 KB	Output is correct
31	Correct	257 ms	19380 KB	Output is correct
32	Correct	240 ms	19544 KB	Output is correct
33	Correct	432 ms	18168 KB	Output is correct
34	Correct	297 ms	19000 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5496 KB	Output is correct
2	Correct	6 ms	5624 KB	Output is correct
3	Correct	5 ms	5596 KB	Output is correct
4	Correct	5 ms	5596 KB	Output is correct
5	Correct	6 ms	5624 KB	Output is correct
6	Correct	5 ms	5624 KB	Output is correct
7	Correct	4 ms	5624 KB	Output is correct
8	Correct	5 ms	5624 KB	Output is correct
9	Correct	5 ms	5624 KB	Output is correct
10	Correct	5 ms	5496 KB	Output is correct
11	Correct	5 ms	5496 KB	Output is correct
12	Correct	5 ms	5624 KB	Output is correct
13	Correct	5 ms	5496 KB	Output is correct
14	Correct	5 ms	5624 KB	Output is correct
15	Correct	5 ms	5624 KB	Output is correct
16	Correct	5 ms	5624 KB	Output is correct
17	Correct	6 ms	5624 KB	Output is correct
18	Correct	5 ms	5624 KB	Output is correct
19	Correct	6 ms	5624 KB	Output is correct
20	Correct	6 ms	5496 KB	Output is correct
21	Correct	7 ms	5624 KB	Output is correct
22	Correct	8 ms	8056 KB	Output is correct
23	Correct	8 ms	7800 KB	Output is correct
24	Correct	9 ms	8440 KB	Output is correct
25	Correct	9 ms	7416 KB	Output is correct
26	Correct	8 ms	6904 KB	Output is correct
27	Correct	6 ms	5624 KB	Output is correct
28	Correct	8 ms	6392 KB	Output is correct
29	Correct	8 ms	6904 KB	Output is correct
30	Correct	8 ms	7032 KB	Output is correct
31	Correct	9 ms	7420 KB	Output is correct
32	Correct	9 ms	7544 KB	Output is correct
33	Correct	10 ms	8312 KB	Output is correct
34	Correct	9 ms	7928 KB	Output is correct
35	Correct	9 ms	8572 KB	Output is correct
36	Correct	9 ms	8952 KB	Output is correct
37	Correct	9 ms	7544 KB	Output is correct
38	Correct	8 ms	6776 KB	Output is correct
39	Correct	204 ms	12252 KB	Output is correct
40	Correct	201 ms	12280 KB	Output is correct
41	Correct	206 ms	12528 KB	Output is correct
42	Correct	186 ms	12724 KB	Output is correct
43	Correct	122 ms	12740 KB	Output is correct
44	Correct	95 ms	12464 KB	Output is correct
45	Correct	210 ms	14208 KB	Output is correct
46	Correct	101 ms	16940 KB	Output is correct
47	Correct	277 ms	19372 KB	Output is correct
48	Correct	506 ms	27512 KB	Output is correct
49	Correct	455 ms	26836 KB	Output is correct
50	Correct	275 ms	19320 KB	Output is correct
51	Correct	257 ms	19380 KB	Output is correct
52	Correct	240 ms	19544 KB	Output is correct
53	Correct	432 ms	18168 KB	Output is correct
54	Correct	297 ms	19000 KB	Output is correct
55	Correct	23 ms	6392 KB	Output is correct
56	Correct	19 ms	6392 KB	Output is correct
57	Correct	124 ms	13012 KB	Output is correct
58	Correct	52 ms	12140 KB	Output is correct
59	Correct	276 ms	20888 KB	Output is correct
60	Correct	1273 ms	38760 KB	Output is correct
61	Correct	317 ms	19832 KB	Output is correct
62	Correct	354 ms	19676 KB	Output is correct
63	Correct	411 ms	19704 KB	Output is correct
64	Correct	1048 ms	26156 KB	Output is correct
65	Correct	250 ms	20344 KB	Output is correct
66	Correct	947 ms	29660 KB	Output is correct
67	Correct	175 ms	20200 KB	Output is correct
68	Correct	501 ms	26516 KB	Output is correct
69	Correct	486 ms	26472 KB	Output is correct
70	Correct	505 ms	25640 KB	Output is correct

답안 #94653

Compilation message

Subtask #1 9.0 / 9.0

Subtask #2 12.0 / 12.0

Subtask #3 22.0 / 22.0

Subtask #4 57.0 / 57.0

Subtask #1
9.0 / 9.0

Subtask #2
12.0 / 12.0

Subtask #3
22.0 / 22.0

Subtask #4
57.0 / 57.0