oj.uz

답안 #29670

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
29670 2017-07-20T10:13:53 Z aybala 꿈 (IOI13_dreaming) C++11
14 / 100
 58 ms 14324 KB 
#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;
	fori(i,0,M){
		v[A[i]].pb(mp(B[i],T[i]));
		v[B[i]].pb(mp(A[i],T[i]));
	}
	
	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;
}

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14324 KB Output is correct
2 Correct 58 ms 14324 KB Output is correct
3 Correct 40 ms 10328 KB Output is correct
4 Correct 11 ms 4480 KB Output is correct
5 Correct 9 ms 3712 KB Output is correct
6 Correct 15 ms 5296 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 27 ms 6904 KB Output is correct
9 Correct 40 ms 8564 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 47 ms 10240 KB Output is correct
12 Correct 53 ms 12268 KB Output is correct
13 Correct 4 ms 2816 KB Output is correct

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14324 KB Output is correct
2 Correct 58 ms 14324 KB Output is correct
3 Correct 40 ms 10328 KB Output is correct
4 Correct 11 ms 4480 KB Output is correct
5 Correct 9 ms 3712 KB Output is correct
6 Correct 15 ms 5296 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 27 ms 6904 KB Output is correct
9 Correct 40 ms 8564 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 47 ms 10240 KB Output is correct
12 Correct 53 ms 12268 KB Output is correct
13 Correct 4 ms 2816 KB Output is correct
14 Runtime error 7 ms 5248 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 54 ms 14324 KB Output is correct
2 Correct 58 ms 14324 KB Output is correct
3 Correct 40 ms 10328 KB Output is correct
4 Correct 11 ms 4480 KB Output is correct
5 Correct 9 ms 3712 KB Output is correct
6 Correct 15 ms 5296 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 27 ms 6904 KB Output is correct
9 Correct 40 ms 8564 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 47 ms 10240 KB Output is correct
12 Correct 53 ms 12268 KB Output is correct
13 Correct 4 ms 2816 KB Output is correct
14 Runtime error 7 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 23 ms 9856 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14324 KB Output is correct
2 Correct 58 ms 14324 KB Output is correct
3 Correct 40 ms 10328 KB Output is correct
4 Correct 11 ms 4480 KB Output is correct
5 Correct 9 ms 3712 KB Output is correct
6 Correct 15 ms 5296 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 27 ms 6904 KB Output is correct
9 Correct 40 ms 8564 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 47 ms 10240 KB Output is correct
12 Correct 53 ms 12268 KB Output is correct
13 Correct 4 ms 2816 KB Output is correct
14 Runtime error 7 ms 5376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 14324 KB Output is correct
2 Correct 58 ms 14324 KB Output is correct
3 Correct 40 ms 10328 KB Output is correct
4 Correct 11 ms 4480 KB Output is correct
5 Correct 9 ms 3712 KB Output is correct
6 Correct 15 ms 5296 KB Output is correct
7 Correct 4 ms 2688 KB Output is correct
8 Correct 27 ms 6904 KB Output is correct
9 Correct 40 ms 8564 KB Output is correct
10 Correct 4 ms 2816 KB Output is correct
11 Correct 47 ms 10240 KB Output is correct
12 Correct 53 ms 12268 KB Output is correct
13 Correct 4 ms 2816 KB Output is correct
14 Runtime error 7 ms 5248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -