답안 #56441 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
56441	2018-07-11T10:44:59 Z	hamzqq9	꿈 (IOI13_dreaming)	C++14	14 / 100	104 ms	32120 KB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define lolo pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define umin(x,y) x=min(x,y)
#define umax(x,y) x=max(x,y)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1002000000
#define LOG 20
#define magic 100
#define MAX 1000005
#define KOK 350
#define EPS 0.000000000001
#define pw(x) (1<<(x))
#define PI 3.1415926535
using namespace std;

vector< pair<int,int> > v[MAX];
int mx[4],deep[MAX];
int cnt,Dcnt;
bool vis[MAX];

void up(int val) {

	mx[2]=val;

	for(int i=2;i>0;i--) {

		if(mx[i]>mx[i-1]) swap(mx[i],mx[i-1]);

	}

}

void dfs3(int node,int ata) {

	deep[node]=0;

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		dfs3(i.st,node);

		if(node==cnt) {

			up(deep[i.st]+i.nd);
		
		}
		else {

			umax(deep[node],deep[i.st]+i.nd);

		}

 	}

}

void dfs2(int node,int ata,int up_max) {

	int Mx[3]={-1,-1,-1};

	int MX=max(deep[node],up_max);

	if(MX<Dcnt) {

		Dcnt=MX;
		cnt=node;

	}

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		Mx[2]=deep[i.st]+i.nd;

		for(int j=2;j>0;j--) {

			if(Mx[j]>Mx[j-1]) swap(Mx[j],Mx[j-1]);

		}

	}

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		int send=(Mx[Mx[0]==deep[i.st]+i.nd]);

		dfs2(i.st,node,max(up_max,send)+i.nd);

	}

}

void dfs1(int node,int ata) {

	deep[node]=0;
	vis[node]=true;

	for(ii i:v[node]) {

		if(i.st==ata) continue ;

		dfs1(i.st,node);

		umax(deep[node],deep[i.st]+i.nd);

	}

}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    
	vector<ii> CMP;

	for(int i=0;i<M;i++) {

		v[A[i]].pb({B[i],T[i]});
		v[B[i]].pb({A[i],T[i]});

	}

	for(int i=0;i<N;i++) {

		if(!vis[i]) {

			dfs1(i,-1);

			Dcnt=inf;

			dfs2(i,-1,0);

		//	printf("%d %d\n",Dcnt,cnt);

			mx[0]=mx[1]=-inf;

			dfs3(cnt,-1);

		//	printf("%d %d\n",mx[0],mx[1]);

			CMP.pb({mx[0],mx[1]});

		}

	}

	int ans=0;

	sort(all(CMP),greater<ii>());

	mx[0]=mx[1]=-inf;

	for(int i=0;i<sz(CMP);i++) {

		umax(ans,CMP[i].st+CMP[i].nd);

		if(i==0) {

			up(CMP[i].st);

		}
		else {

			up(CMP[i].st+L);

		}

	}

	umax(ans,mx[0]+mx[1]);

	return ans;

}
/*
int main() {

	freopen("read.txt","r",stdin);

	int a[55],b[55],t[55],L,N,M;

	scanf("%d %d %d",&N,&M,&L);

	for(int i=0;i<M;i++) {

		scanf("%d %d %d",&a[i],&b[i],&t[i]);

	}

	printf("%d\n",travelTime(N,M,L,a,b,t));

}*/

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	32120 KB	Output is correct
2	Correct	81 ms	31868 KB	Output is correct
3	Correct	60 ms	30712 KB	Output is correct
4	Correct	31 ms	25088 KB	Output is correct
5	Correct	33 ms	24568 KB	Output is correct
6	Correct	35 ms	25724 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	87 ms	27256 KB	Output is correct
9	Correct	58 ms	29304 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	104 ms	29852 KB	Output is correct
12	Correct	99 ms	30968 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	32120 KB	Output is correct
2	Correct	81 ms	31868 KB	Output is correct
3	Correct	60 ms	30712 KB	Output is correct
4	Correct	31 ms	25088 KB	Output is correct
5	Correct	33 ms	24568 KB	Output is correct
6	Correct	35 ms	25724 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	87 ms	27256 KB	Output is correct
9	Correct	58 ms	29304 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	104 ms	29852 KB	Output is correct
12	Correct	99 ms	30968 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	22 ms	23808 KB	Output is correct
16	Correct	20 ms	23808 KB	Output is correct
17	Correct	21 ms	23800 KB	Output is correct
18	Correct	21 ms	23808 KB	Output is correct
19	Correct	21 ms	23808 KB	Output is correct
20	Correct	23 ms	23800 KB	Output is correct
21	Correct	21 ms	23808 KB	Output is correct
22	Correct	22 ms	23808 KB	Output is correct
23	Correct	21 ms	23808 KB	Output is correct
24	Correct	22 ms	23800 KB	Output is correct
25	Correct	23 ms	23808 KB	Output is correct
26	Correct	20 ms	23772 KB	Output is correct
27	Correct	21 ms	23880 KB	Output is correct
28	Incorrect	21 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	32120 KB	Output is correct
2	Correct	81 ms	31868 KB	Output is correct
3	Correct	60 ms	30712 KB	Output is correct
4	Correct	31 ms	25088 KB	Output is correct
5	Correct	33 ms	24568 KB	Output is correct
6	Correct	35 ms	25724 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	87 ms	27256 KB	Output is correct
9	Correct	58 ms	29304 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	104 ms	29852 KB	Output is correct
12	Correct	99 ms	30968 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	22 ms	23808 KB	Output is correct
16	Correct	20 ms	23808 KB	Output is correct
17	Correct	21 ms	23800 KB	Output is correct
18	Correct	21 ms	23808 KB	Output is correct
19	Correct	21 ms	23808 KB	Output is correct
20	Correct	23 ms	23800 KB	Output is correct
21	Correct	21 ms	23808 KB	Output is correct
22	Correct	22 ms	23808 KB	Output is correct
23	Correct	21 ms	23808 KB	Output is correct
24	Correct	22 ms	23800 KB	Output is correct
25	Correct	23 ms	23808 KB	Output is correct
26	Correct	20 ms	23772 KB	Output is correct
27	Correct	21 ms	23880 KB	Output is correct
28	Incorrect	21 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	27328 KB	Output is correct
2	Correct	47 ms	27324 KB	Output is correct
3	Correct	47 ms	27300 KB	Output is correct
4	Correct	50 ms	27304 KB	Output is correct
5	Correct	47 ms	27256 KB	Output is correct
6	Correct	49 ms	28028 KB	Output is correct
7	Correct	47 ms	27384 KB	Output is correct
8	Correct	47 ms	27256 KB	Output is correct
9	Correct	46 ms	27124 KB	Output is correct
10	Correct	55 ms	27380 KB	Output is correct
11	Correct	21 ms	23808 KB	Output is correct
12	Correct	27 ms	25592 KB	Output is correct
13	Correct	27 ms	25464 KB	Output is correct
14	Correct	28 ms	25464 KB	Output is correct
15	Correct	27 ms	25464 KB	Output is correct
16	Correct	28 ms	25444 KB	Output is correct
17	Correct	26 ms	25456 KB	Output is correct
18	Correct	29 ms	25592 KB	Output is correct
19	Correct	29 ms	25464 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Incorrect	21 ms	23808 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	32120 KB	Output is correct
2	Correct	81 ms	31868 KB	Output is correct
3	Correct	60 ms	30712 KB	Output is correct
4	Correct	31 ms	25088 KB	Output is correct
5	Correct	33 ms	24568 KB	Output is correct
6	Correct	35 ms	25724 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	87 ms	27256 KB	Output is correct
9	Correct	58 ms	29304 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	104 ms	29852 KB	Output is correct
12	Correct	99 ms	30968 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	21 ms	23808 KB	Output is correct
15	Correct	22 ms	23936 KB	Output is correct
16	Correct	23 ms	23936 KB	Output is correct
17	Correct	21 ms	23856 KB	Output is correct
18	Correct	22 ms	23936 KB	Output is correct
19	Correct	24 ms	23936 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	24 ms	23936 KB	Output is correct
22	Correct	26 ms	24064 KB	Output is correct
23	Correct	21 ms	23808 KB	Output is correct
24	Correct	21 ms	23808 KB	Output is correct
25	Correct	21 ms	23808 KB	Output is correct
26	Correct	21 ms	23808 KB	Output is correct
27	Correct	22 ms	23800 KB	Output is correct
28	Correct	21 ms	23928 KB	Output is correct
29	Correct	22 ms	23804 KB	Output is correct
30	Correct	22 ms	23808 KB	Output is correct
31	Correct	23 ms	23800 KB	Output is correct
32	Correct	21 ms	23808 KB	Output is correct
33	Correct	21 ms	23936 KB	Output is correct
34	Correct	21 ms	23808 KB	Output is correct
35	Correct	21 ms	23800 KB	Output is correct
36	Correct	22 ms	23808 KB	Output is correct
37	Correct	21 ms	23928 KB	Output is correct
38	Correct	21 ms	23808 KB	Output is correct
39	Correct	22 ms	23808 KB	Output is correct
40	Correct	21 ms	23808 KB	Output is correct
41	Incorrect	21 ms	23808 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	32120 KB	Output is correct
2	Correct	81 ms	31868 KB	Output is correct
3	Correct	60 ms	30712 KB	Output is correct
4	Correct	31 ms	25088 KB	Output is correct
5	Correct	33 ms	24568 KB	Output is correct
6	Correct	35 ms	25724 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	87 ms	27256 KB	Output is correct
9	Correct	58 ms	29304 KB	Output is correct
10	Correct	24 ms	23928 KB	Output is correct
11	Correct	104 ms	29852 KB	Output is correct
12	Correct	99 ms	30968 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	24 ms	23808 KB	Output is correct
15	Correct	22 ms	23808 KB	Output is correct
16	Correct	20 ms	23808 KB	Output is correct
17	Correct	21 ms	23800 KB	Output is correct
18	Correct	21 ms	23808 KB	Output is correct
19	Correct	21 ms	23808 KB	Output is correct
20	Correct	23 ms	23800 KB	Output is correct
21	Correct	21 ms	23808 KB	Output is correct
22	Correct	22 ms	23808 KB	Output is correct
23	Correct	21 ms	23808 KB	Output is correct
24	Correct	22 ms	23800 KB	Output is correct
25	Correct	23 ms	23808 KB	Output is correct
26	Correct	20 ms	23772 KB	Output is correct
27	Correct	21 ms	23880 KB	Output is correct
28	Incorrect	21 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #56441

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 0 / 10.0

Subtask #3 0 / 23.0

Subtask #4 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
0 / 18.0

Subtask #5
0 / 12.0

Subtask #6
0 / 23.0