답안 #147335

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147335	2019-08-28T20:45:00 Z	mosiashvililuka	경주 (Race) (IOI11_race)	C++14	100 / 100	855 ms	49272 KB

race

#include<bits/stdc++.h>
#include "race.h"
#define mk make_pair
#define pll pair <long long, long long> 
using namespace std;
long long a,b,c,d,e,pas=999999999999999999LL,k,pi,p[200009],dp[200009],cnt,dep[200009],msh[200009],koka;
bool was[200009];
vector <pair <long long, long long> > v[200009];
pair <long long, long long> z[1000009];
void dfs(long long q, long long w){
	pi++;
	p[pi]=q;
	dp[q]=1;
	msh[q]=w;
	for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w||was[(*it).first]==1) continue;
		dfs((*it).first,q);
		dp[q]+=dp[(*it).first];
	}
}
void dfs2(long long q, long long w, long long r){
	dep[q]=dep[w]+1;
	if(r<=k&&z[k-r].second==cnt){
		if(pas>dep[q]+z[k-r].first){
//		    cout<<q<<" "<<z[k-r].second<<" "<<koka<<endl;
		    pas=dep[q]+z[k-r].first;
		}
	}
	for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w||was[(*it).first]==1) continue;
		dfs2((*it).first,q,(*it).second+r);
	}
}
void dfs3(long long q, long long w, long long r){
	if(r<=k){
		if(z[r].second==cnt){
			if(z[r].first>dep[q]) z[r].first=dep[q];
		}else{
			z[r].first=dep[q];
			z[r].second=cnt;
		}
	}
	for(vector <pll>::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w||was[(*it).first]==1) continue;
		dfs3((*it).first,q,(*it).second+r);
	}
}
void rec(long long q){
	cnt++;
	pi=0;
	dfs(q,0);
	long long zx=0;
	for(long long h=1; h<=pi; h++){
		bool bo=0;
		for(vector <pll>::iterator it=v[p[h]].begin(); it!=v[p[h]].end(); it++){
		   if(was[(*it).first]==1||msh[p[h]]==(*it).first) continue;
		if(dp[(*it).first]>pi/2){
			bo=1;
			break;
		}
		}
		if(pi-dp[p[h]]>pi/2) bo=1;
		if(bo==0){
			zx=p[h];
			break;
		}
	}
	z[0].first=0;
	z[0].second=cnt;
	dep[zx]=0;koka=zx;
	for(vector <pll>::iterator it=v[zx].begin(); it!=v[zx].end(); it++){
		if(was[(*it).first]==0) dfs2((*it).first,zx,(*it).second);
		if(was[(*it).first]==0) dfs3((*it).first,zx,(*it).second);
	}
	was[zx]=1;
	for(vector <pll>::iterator it=v[zx].begin(); it!=v[zx].end(); it++){
	    if(was[(*it).first]==0) rec((*it).first);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	//cin>>a>>k;
	a=N;k=K;
	for(b=1; b<a; b++){
		//cin>>c>>d>>e;
		c=H[b-1][0];d=H[b-1][1];e=L[b-1];
		c++;
		d++;
		v[c].push_back(mk(d,e));
		v[d].push_back(mk(c,e));
	}
	rec(1);
	if(pas==999999999999999999LL) return -1; else return pas;
	return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	6 ms	5116 KB	Output is correct
3	Correct	6 ms	5112 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	6 ms	5112 KB	Output is correct
6	Correct	6 ms	5112 KB	Output is correct
7	Correct	6 ms	5112 KB	Output is correct
8	Correct	6 ms	5112 KB	Output is correct
9	Correct	6 ms	5112 KB	Output is correct
10	Correct	6 ms	5112 KB	Output is correct
11	Correct	7 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	5112 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	7 ms	5116 KB	Output is correct
16	Correct	7 ms	5112 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct
18	Correct	6 ms	5112 KB	Output is correct
19	Correct	6 ms	4984 KB	Output is correct
20	Correct	6 ms	5112 KB	Output is correct
21	Correct	7 ms	5116 KB	Output is correct
22	Correct	13 ms	9208 KB	Output is correct
23	Correct	12 ms	8696 KB	Output is correct
24	Correct	14 ms	10232 KB	Output is correct
25	Correct	15 ms	10744 KB	Output is correct
26	Correct	12 ms	8696 KB	Output is correct
27	Correct	7 ms	5240 KB	Output is correct
28	Correct	10 ms	8184 KB	Output is correct
29	Correct	12 ms	9592 KB	Output is correct
30	Correct	13 ms	10104 KB	Output is correct
31	Correct	15 ms	10876 KB	Output is correct
32	Correct	15 ms	10868 KB	Output is correct
33	Correct	18 ms	13304 KB	Output is correct
34	Correct	16 ms	11640 KB	Output is correct
35	Correct	17 ms	12792 KB	Output is correct
36	Correct	18 ms	13044 KB	Output is correct
37	Correct	14 ms	10232 KB	Output is correct
38	Correct	13 ms	8952 KB	Output is correct

Subtask #3
22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	6 ms	5116 KB	Output is correct
3	Correct	6 ms	5112 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	6 ms	5112 KB	Output is correct
6	Correct	6 ms	5112 KB	Output is correct
7	Correct	6 ms	5112 KB	Output is correct
8	Correct	6 ms	5112 KB	Output is correct
9	Correct	6 ms	5112 KB	Output is correct
10	Correct	6 ms	5112 KB	Output is correct
11	Correct	7 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	5112 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	7 ms	5116 KB	Output is correct
16	Correct	7 ms	5112 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct
18	Correct	6 ms	5112 KB	Output is correct
19	Correct	202 ms	15864 KB	Output is correct
20	Correct	215 ms	15992 KB	Output is correct
21	Correct	234 ms	16088 KB	Output is correct
22	Correct	176 ms	15992 KB	Output is correct
23	Correct	221 ms	16324 KB	Output is correct
24	Correct	97 ms	15608 KB	Output is correct
25	Correct	207 ms	18108 KB	Output is correct
26	Correct	108 ms	20216 KB	Output is correct
27	Correct	239 ms	27384 KB	Output is correct
28	Correct	523 ms	35648 KB	Output is correct
29	Correct	547 ms	35108 KB	Output is correct
30	Correct	237 ms	27532 KB	Output is correct
31	Correct	240 ms	27368 KB	Output is correct
32	Correct	328 ms	27516 KB	Output is correct
33	Correct	434 ms	26232 KB	Output is correct
34	Correct	421 ms	27272 KB	Output is correct

Subtask #4
57.0 / 57.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5112 KB	Output is correct
2	Correct	6 ms	5116 KB	Output is correct
3	Correct	6 ms	5112 KB	Output is correct
4	Correct	6 ms	5112 KB	Output is correct
5	Correct	6 ms	5112 KB	Output is correct
6	Correct	6 ms	5112 KB	Output is correct
7	Correct	6 ms	5112 KB	Output is correct
8	Correct	6 ms	5112 KB	Output is correct
9	Correct	6 ms	5112 KB	Output is correct
10	Correct	6 ms	5112 KB	Output is correct
11	Correct	7 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	5112 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	7 ms	5116 KB	Output is correct
16	Correct	7 ms	5112 KB	Output is correct
17	Correct	6 ms	5112 KB	Output is correct
18	Correct	6 ms	5112 KB	Output is correct
19	Correct	6 ms	4984 KB	Output is correct
20	Correct	6 ms	5112 KB	Output is correct
21	Correct	7 ms	5116 KB	Output is correct
22	Correct	13 ms	9208 KB	Output is correct
23	Correct	12 ms	8696 KB	Output is correct
24	Correct	14 ms	10232 KB	Output is correct
25	Correct	15 ms	10744 KB	Output is correct
26	Correct	12 ms	8696 KB	Output is correct
27	Correct	7 ms	5240 KB	Output is correct
28	Correct	10 ms	8184 KB	Output is correct
29	Correct	12 ms	9592 KB	Output is correct
30	Correct	13 ms	10104 KB	Output is correct
31	Correct	15 ms	10876 KB	Output is correct
32	Correct	15 ms	10868 KB	Output is correct
33	Correct	18 ms	13304 KB	Output is correct
34	Correct	16 ms	11640 KB	Output is correct
35	Correct	17 ms	12792 KB	Output is correct
36	Correct	18 ms	13044 KB	Output is correct
37	Correct	14 ms	10232 KB	Output is correct
38	Correct	13 ms	8952 KB	Output is correct
39	Correct	202 ms	15864 KB	Output is correct
40	Correct	215 ms	15992 KB	Output is correct
41	Correct	234 ms	16088 KB	Output is correct
42	Correct	176 ms	15992 KB	Output is correct
43	Correct	221 ms	16324 KB	Output is correct
44	Correct	97 ms	15608 KB	Output is correct
45	Correct	207 ms	18108 KB	Output is correct
46	Correct	108 ms	20216 KB	Output is correct
47	Correct	239 ms	27384 KB	Output is correct
48	Correct	523 ms	35648 KB	Output is correct
49	Correct	547 ms	35108 KB	Output is correct
50	Correct	237 ms	27532 KB	Output is correct
51	Correct	240 ms	27368 KB	Output is correct
52	Correct	328 ms	27516 KB	Output is correct
53	Correct	434 ms	26232 KB	Output is correct
54	Correct	421 ms	27272 KB	Output is correct
55	Correct	18 ms	6264 KB	Output is correct
56	Correct	18 ms	6136 KB	Output is correct
57	Correct	96 ms	16376 KB	Output is correct
58	Correct	50 ms	15204 KB	Output is correct
59	Correct	120 ms	21752 KB	Output is correct
60	Correct	573 ms	44540 KB	Output is correct
61	Correct	265 ms	27768 KB	Output is correct
62	Correct	295 ms	27640 KB	Output is correct
63	Correct	359 ms	27768 KB	Output is correct
64	Correct	674 ms	31864 KB	Output is correct
65	Correct	447 ms	28024 KB	Output is correct
66	Correct	855 ms	49272 KB	Output is correct
67	Correct	170 ms	26672 KB	Output is correct
68	Correct	347 ms	38108 KB	Output is correct
69	Correct	354 ms	38264 KB	Output is correct
70	Correct	329 ms	36984 KB	Output is correct

답안 #147335

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