답안 #29736 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29736	2017-07-20T11:50:50 Z	aybala	꿈 (IOI13_dreaming)	C++11	32 / 100	63 ms	14324 KB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define fori(a,b,c) for(int a=b; a<c; a++)
#define ford(a,b,c) for(int a=b; a>=c; a++)
#define pb push_back
#define pq priority_queue
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define ll long long
using namespace std;
vector< pii >v[100004];
ll dis[100004];
ll disr[100004];
vector< int >el[2];
bool vis[100004];
ll ans[2][2];

void dfs(int u, int pre, int gr){
	int s=v[u].size();
	vis[u]=1;
	el[gr].pb(u);
	fori(i,0,s){
		if(pre!=v[u][i].fi){
			dis[v[u][i].fi]+=dis[u]+v[u][i].se;
			dfs(v[u][i].fi,u,gr);	
		}
	}
}


int n;
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n=N;
	int max1=0;
	int max2=0;
	int max3=0;
	fori(i,0,M){
		v[A[i]].pb(mp(B[i],T[i]));
		v[B[i]].pb(mp(A[i],T[i]));
		if(T[i]>=max1){
			max3=max2;
			max2=max1;
			max1=T[i];
		}
		else if(T[i]>=max2){
			max3=max2;
			max2=T[i];
		}
		else if(T[i]>=max3){
			max3=T[i];
		}
	}
	
	fori(i,0,n){
		if(v[i].size()>=2){
			if(M==N-2){
		int gr=0;
		fori(i,0,n){
			if(v[i].size()==1 && !vis[i]){
				dfs(i,i,gr);
				int s=el[gr].size();
				int uu=el[gr][s-1];
				fori(j,0,s){
					disr[el[gr][j]]=dis[uu]-dis[el[gr][j]];
					if(j==0){
						ans[gr][0]=el[gr][j];
						ans[gr][1]=max(disr[el[gr][j]],dis[el[gr][j]]);
					}
					else if(ans[gr][1]>max(disr[el[gr][j]],dis[el[gr][j]])){
						ans[gr][1]=max(disr[el[gr][j]],dis[el[gr][j]]);
						ans[gr][0]=el[gr][j];
					}
				}
				gr++;
			}
		}
		ll res=0;
		fori(i,0,2){
			int u = el[i][0];
			res=max(res,disr[u]);
			res=max(res,dis[ans[i][0]]+L+ans[(i+1)%2][1]);
	
			u = el[i][el[i].size()-1];
			res=max(res,dis[u]);
			res=max(res,disr[ans[i][0]]+L+ans[(i+1)%2][1]);
		}
		return res;	
	}
	
		}
	}
	
	
	if(n==1)
		return 0;
	if(n==2 && v[0].size()==1)
		return max1;
	if(n==2 && v[0].size()==0)
		return L;
	if(n==3 && max1!=0)
		return max1+L;
	if(!max2){
		return max(max1+L, 2*L);
	}
	return max(max3+max2+2*L, max1+max2+L);
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	14324 KB	Output is correct
2	Correct	63 ms	14324 KB	Output is correct
3	Correct	42 ms	10356 KB	Output is correct
4	Correct	11 ms	4480 KB	Output is correct
5	Correct	9 ms	3712 KB	Output is correct
6	Correct	16 ms	5396 KB	Output is correct
7	Correct	4 ms	2816 KB	Output is correct
8	Correct	29 ms	6912 KB	Output is correct
9	Correct	34 ms	8500 KB	Output is correct
10	Correct	5 ms	2816 KB	Output is correct
11	Correct	56 ms	10228 KB	Output is correct
12	Correct	59 ms	12276 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	14324 KB	Output is correct
2	Correct	63 ms	14324 KB	Output is correct
3	Correct	42 ms	10356 KB	Output is correct
4	Correct	11 ms	4480 KB	Output is correct
5	Correct	9 ms	3712 KB	Output is correct
6	Correct	16 ms	5396 KB	Output is correct
7	Correct	4 ms	2816 KB	Output is correct
8	Correct	29 ms	6912 KB	Output is correct
9	Correct	34 ms	8500 KB	Output is correct
10	Correct	5 ms	2816 KB	Output is correct
11	Correct	56 ms	10228 KB	Output is correct
12	Correct	59 ms	12276 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Runtime error	7 ms	5120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	14324 KB	Output is correct
2	Correct	63 ms	14324 KB	Output is correct
3	Correct	42 ms	10356 KB	Output is correct
4	Correct	11 ms	4480 KB	Output is correct
5	Correct	9 ms	3712 KB	Output is correct
6	Correct	16 ms	5396 KB	Output is correct
7	Correct	4 ms	2816 KB	Output is correct
8	Correct	29 ms	6912 KB	Output is correct
9	Correct	34 ms	8500 KB	Output is correct
10	Correct	5 ms	2816 KB	Output is correct
11	Correct	56 ms	10228 KB	Output is correct
12	Correct	59 ms	12276 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Runtime error	7 ms	5120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	21 ms	4992 KB	Output is correct
2	Correct	20 ms	4992 KB	Output is correct
3	Correct	21 ms	5012 KB	Output is correct
4	Correct	22 ms	4992 KB	Output is correct
5	Correct	22 ms	4992 KB	Output is correct
6	Correct	23 ms	5120 KB	Output is correct
7	Correct	20 ms	5120 KB	Output is correct
8	Correct	20 ms	4984 KB	Output is correct
9	Correct	19 ms	4984 KB	Output is correct
10	Correct	23 ms	5120 KB	Output is correct
11	Correct	4 ms	2688 KB	Output is correct
12	Correct	4 ms	2688 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Correct	4 ms	2688 KB	Output is correct
15	Correct	4 ms	2688 KB	Output is correct
16	Correct	4 ms	2688 KB	Output is correct
17	Correct	4 ms	2688 KB	Output is correct
18	Correct	4 ms	2688 KB	Output is correct
19	Correct	4 ms	2688 KB	Output is correct
20	Correct	3 ms	2688 KB	Output is correct
21	Correct	4 ms	2688 KB	Output is correct
22	Correct	4 ms	2688 KB	Output is correct
23	Correct	4 ms	2688 KB	Output is correct

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	14324 KB	Output is correct
2	Correct	63 ms	14324 KB	Output is correct
3	Correct	42 ms	10356 KB	Output is correct
4	Correct	11 ms	4480 KB	Output is correct
5	Correct	9 ms	3712 KB	Output is correct
6	Correct	16 ms	5396 KB	Output is correct
7	Correct	4 ms	2816 KB	Output is correct
8	Correct	29 ms	6912 KB	Output is correct
9	Correct	34 ms	8500 KB	Output is correct
10	Correct	5 ms	2816 KB	Output is correct
11	Correct	56 ms	10228 KB	Output is correct
12	Correct	59 ms	12276 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Incorrect	4 ms	2688 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	57 ms	14324 KB	Output is correct
2	Correct	63 ms	14324 KB	Output is correct
3	Correct	42 ms	10356 KB	Output is correct
4	Correct	11 ms	4480 KB	Output is correct
5	Correct	9 ms	3712 KB	Output is correct
6	Correct	16 ms	5396 KB	Output is correct
7	Correct	4 ms	2816 KB	Output is correct
8	Correct	29 ms	6912 KB	Output is correct
9	Correct	34 ms	8500 KB	Output is correct
10	Correct	5 ms	2816 KB	Output is correct
11	Correct	56 ms	10228 KB	Output is correct
12	Correct	59 ms	12276 KB	Output is correct
13	Correct	4 ms	2816 KB	Output is correct
14	Runtime error	7 ms	5120 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

답안 #29736

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 0 / 10.0

Subtask #3 0 / 23.0

Subtask #4 18.0 / 18.0

Subtask #5 0 / 12.0

Subtask #6 0 / 23.0

Subtask #1
14.0 / 14.0

Subtask #2
0 / 10.0

Subtask #3
0 / 23.0

Subtask #4
18.0 / 18.0

Subtask #5
0 / 12.0

Subtask #6
0 / 23.0