답안 #147336

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
147336	2019-08-28T20:46:59 Z	mosiashvililuka	경주 (Race) (IOI11_race)	C++14	100 / 100	627 ms	46216 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 za, int xa, int ca[][2], int va[]){
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	//cin>>a>>k;
	a=za;k=xa;
	for(b=1; b<a; b++){
		//cin>>c>>d>>e;
		c=ca[b-1][0];d=ca[b-1][1];e=va[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	5112 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	6 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	4984 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	6 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	4984 KB	Output is correct
18	Correct	6 ms	4988 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	5112 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	6 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	4984 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	6 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	4984 KB	Output is correct
18	Correct	6 ms	4988 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	5112 KB	Output is correct
22	Correct	13 ms	9208 KB	Output is correct
23	Correct	32 ms	8568 KB	Output is correct
24	Correct	14 ms	10232 KB	Output is correct
25	Correct	15 ms	10616 KB	Output is correct
26	Correct	11 ms	8696 KB	Output is correct
27	Correct	7 ms	5112 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	10744 KB	Output is correct
32	Correct	15 ms	10872 KB	Output is correct
33	Correct	18 ms	13304 KB	Output is correct
34	Correct	15 ms	11516 KB	Output is correct
35	Correct	17 ms	12540 KB	Output is correct
36	Correct	18 ms	13048 KB	Output is correct
37	Correct	14 ms	10232 KB	Output is correct
38	Correct	12 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	5112 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	6 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	4984 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	6 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	4984 KB	Output is correct
18	Correct	6 ms	4988 KB	Output is correct
19	Correct	196 ms	14640 KB	Output is correct
20	Correct	191 ms	14712 KB	Output is correct
21	Correct	193 ms	14612 KB	Output is correct
22	Correct	171 ms	14588 KB	Output is correct
23	Correct	172 ms	15104 KB	Output is correct
24	Correct	112 ms	14328 KB	Output is correct
25	Correct	199 ms	16568 KB	Output is correct
26	Correct	108 ms	18808 KB	Output is correct
27	Correct	260 ms	24672 KB	Output is correct
28	Correct	541 ms	32632 KB	Output is correct
29	Correct	530 ms	31992 KB	Output is correct
30	Correct	240 ms	24568 KB	Output is correct
31	Correct	240 ms	24568 KB	Output is correct
32	Correct	320 ms	24568 KB	Output is correct
33	Correct	427 ms	23360 KB	Output is correct
34	Correct	500 ms	23296 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	5112 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	6 ms	5112 KB	Output is correct
12	Correct	6 ms	5112 KB	Output is correct
13	Correct	6 ms	4984 KB	Output is correct
14	Correct	6 ms	5112 KB	Output is correct
15	Correct	6 ms	5112 KB	Output is correct
16	Correct	6 ms	4984 KB	Output is correct
17	Correct	6 ms	4984 KB	Output is correct
18	Correct	6 ms	4988 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	5112 KB	Output is correct
22	Correct	13 ms	9208 KB	Output is correct
23	Correct	32 ms	8568 KB	Output is correct
24	Correct	14 ms	10232 KB	Output is correct
25	Correct	15 ms	10616 KB	Output is correct
26	Correct	11 ms	8696 KB	Output is correct
27	Correct	7 ms	5112 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	10744 KB	Output is correct
32	Correct	15 ms	10872 KB	Output is correct
33	Correct	18 ms	13304 KB	Output is correct
34	Correct	15 ms	11516 KB	Output is correct
35	Correct	17 ms	12540 KB	Output is correct
36	Correct	18 ms	13048 KB	Output is correct
37	Correct	14 ms	10232 KB	Output is correct
38	Correct	12 ms	8952 KB	Output is correct
39	Correct	196 ms	14640 KB	Output is correct
40	Correct	191 ms	14712 KB	Output is correct
41	Correct	193 ms	14612 KB	Output is correct
42	Correct	171 ms	14588 KB	Output is correct
43	Correct	172 ms	15104 KB	Output is correct
44	Correct	112 ms	14328 KB	Output is correct
45	Correct	199 ms	16568 KB	Output is correct
46	Correct	108 ms	18808 KB	Output is correct
47	Correct	260 ms	24672 KB	Output is correct
48	Correct	541 ms	32632 KB	Output is correct
49	Correct	530 ms	31992 KB	Output is correct
50	Correct	240 ms	24568 KB	Output is correct
51	Correct	240 ms	24568 KB	Output is correct
52	Correct	320 ms	24568 KB	Output is correct
53	Correct	427 ms	23360 KB	Output is correct
54	Correct	500 ms	23296 KB	Output is correct
55	Correct	18 ms	6136 KB	Output is correct
56	Correct	18 ms	6048 KB	Output is correct
57	Correct	95 ms	14968 KB	Output is correct
58	Correct	52 ms	14180 KB	Output is correct
59	Correct	120 ms	20472 KB	Output is correct
60	Correct	563 ms	41592 KB	Output is correct
61	Correct	255 ms	24704 KB	Output is correct
62	Correct	242 ms	24552 KB	Output is correct
63	Correct	318 ms	24568 KB	Output is correct
64	Correct	603 ms	28280 KB	Output is correct
65	Correct	439 ms	24244 KB	Output is correct
66	Correct	627 ms	46216 KB	Output is correct
67	Correct	152 ms	23260 KB	Output is correct
68	Correct	373 ms	34496 KB	Output is correct
69	Correct	351 ms	34552 KB	Output is correct
70	Correct	339 ms	33468 KB	Output is correct

답안 #147336

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