답안 #17152 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17152	2015-11-07T08:18:52 Z	murat	꿈 (IOI13_dreaming)	C++	14 / 100	146 ms	35616 KB

dreaming

#include<bits/stdc++.h>
#include "dreaming.h"

using namespace std;

#define foreach(it, x) for(type(x) it = x.begin(); it != x.end(); it++)
#define type(x) __typeof(x.begin())
#define pb push_back
#define mp make_pair
#define nd second
#define st first

const int N = 1e6 + 5;
const int inf = 1e9 + 5;

typedef pair< int , int > pii;

int n, m, x, y, z, val[N], h[N];
vector< pii > v[N];

pii dfs(int node, int root = 0) {
    pii tt = mp(0, node);
    foreach(it, v[node])
        if(it->st != root) {
            pii temp = dfs(it->st, node);
            temp.st += it->nd;
            tt = max(tt, temp);
        }
    return tt;
}

void dfs2(int node, int root = 0, int dist = 0) {
    val[node] = max(val[node], dist);
    foreach(it, v[node])
        if(it->st != root)
            dfs2(it->st, node, dist + it->nd);
}

int take(int node, int root = 0) {
    int nnn = node;
    h[node] = 1;
    foreach(it, v[node])
        if(it->st != root) {
            int ttt = take(it->st, node);
            if(val[ttt] < val[nnn])
                nnn = ttt;
        }
    return nnn;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {

    n = N;
    val[n] = inf * 2;

    for(int i = 0; i < M; i++) {
        int x = A[i], y = B[i], z = T[i];
        v[x].pb(mp(y, z));
        v[y].pb(mp(x, z));
    }
	
  	priority_queue< pii > q;


    for(int i = 0; i < N; i++) {
        if(!h[i]) {
            int x = dfs(i).nd, y = dfs(x).nd;
            dfs2(x); dfs2(y);
            int nnn = take(i);
            q.push(mp(val[nnn], nnn));
        }
    }

    while(q.size() > 1) {
        pii t1 = q.top(); q.pop();
        pii t2 = q.top(); q.pop();
        int q1 = max(t1.st, t2.st + L);
        int q2 = max(t1.st + L, t2.st);
        v[t1.nd].pb(mp(t2.nd, L));
        v[t2.nd].pb(mp(t1.nd, L));
        pii tt;
        if(q1 < q2) q.push(tt =mp(q1, t1.nd));
        else q.push(tt = mp(q2, t2.nd));
    }


    int x = dfs(0).nd, ans = dfs(x).st;

    return ans;
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	109 ms	35576 KB	Output is correct
2	Correct	146 ms	35616 KB	Output is correct
3	Correct	70 ms	31480 KB	Output is correct
4	Correct	32 ms	25464 KB	Output is correct
5	Correct	31 ms	24728 KB	Output is correct
6	Correct	41 ms	26360 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	66 ms	27796 KB	Output is correct
9	Correct	72 ms	29432 KB	Output is correct
10	Correct	22 ms	23936 KB	Output is correct
11	Correct	101 ms	31096 KB	Output is correct
12	Correct	108 ms	33272 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	109 ms	35576 KB	Output is correct
2	Correct	146 ms	35616 KB	Output is correct
3	Correct	70 ms	31480 KB	Output is correct
4	Correct	32 ms	25464 KB	Output is correct
5	Correct	31 ms	24728 KB	Output is correct
6	Correct	41 ms	26360 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	66 ms	27796 KB	Output is correct
9	Correct	72 ms	29432 KB	Output is correct
10	Correct	22 ms	23936 KB	Output is correct
11	Correct	101 ms	31096 KB	Output is correct
12	Correct	108 ms	33272 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	22 ms	23808 KB	Output is correct
15	Correct	21 ms	23792 KB	Output is correct
16	Correct	21 ms	23808 KB	Output is correct
17	Correct	22 ms	23808 KB	Output is correct
18	Correct	24 ms	23808 KB	Output is correct
19	Correct	21 ms	23808 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	22 ms	23876 KB	Output is correct
22	Correct	21 ms	23808 KB	Output is correct
23	Correct	23 ms	23880 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	23808 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	109 ms	35576 KB	Output is correct
2	Correct	146 ms	35616 KB	Output is correct
3	Correct	70 ms	31480 KB	Output is correct
4	Correct	32 ms	25464 KB	Output is correct
5	Correct	31 ms	24728 KB	Output is correct
6	Correct	41 ms	26360 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	66 ms	27796 KB	Output is correct
9	Correct	72 ms	29432 KB	Output is correct
10	Correct	22 ms	23936 KB	Output is correct
11	Correct	101 ms	31096 KB	Output is correct
12	Correct	108 ms	33272 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	22 ms	23808 KB	Output is correct
15	Correct	21 ms	23792 KB	Output is correct
16	Correct	21 ms	23808 KB	Output is correct
17	Correct	22 ms	23808 KB	Output is correct
18	Correct	24 ms	23808 KB	Output is correct
19	Correct	21 ms	23808 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	22 ms	23876 KB	Output is correct
22	Correct	21 ms	23808 KB	Output is correct
23	Correct	23 ms	23880 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	23808 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	86 ms	28848 KB	Output is correct
2	Correct	71 ms	28924 KB	Output is correct
3	Correct	78 ms	28788 KB	Output is correct
4	Correct	86 ms	28800 KB	Output is correct
5	Correct	88 ms	28752 KB	Output is correct
6	Correct	83 ms	29652 KB	Output is correct
7	Correct	76 ms	29048 KB	Output is correct
8	Correct	85 ms	28840 KB	Output is correct
9	Correct	76 ms	28732 KB	Output is correct
10	Correct	87 ms	29072 KB	Output is correct
11	Correct	22 ms	23936 KB	Output is correct
12	Correct	56 ms	29292 KB	Output is correct
13	Correct	58 ms	29288 KB	Output is correct
14	Correct	57 ms	29292 KB	Output is correct
15	Correct	57 ms	29288 KB	Output is correct
16	Correct	58 ms	29420 KB	Output is correct
17	Correct	57 ms	29292 KB	Output is correct
18	Correct	59 ms	29300 KB	Output is correct
19	Correct	56 ms	29288 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	109 ms	35576 KB	Output is correct
2	Correct	146 ms	35616 KB	Output is correct
3	Correct	70 ms	31480 KB	Output is correct
4	Correct	32 ms	25464 KB	Output is correct
5	Correct	31 ms	24728 KB	Output is correct
6	Correct	41 ms	26360 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	66 ms	27796 KB	Output is correct
9	Correct	72 ms	29432 KB	Output is correct
10	Correct	22 ms	23936 KB	Output is correct
11	Correct	101 ms	31096 KB	Output is correct
12	Correct	108 ms	33272 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	22 ms	23936 KB	Output is correct
15	Correct	24 ms	23888 KB	Output is correct
16	Correct	22 ms	23936 KB	Output is correct
17	Correct	22 ms	23936 KB	Output is correct
18	Correct	24 ms	23936 KB	Output is correct
19	Correct	23 ms	23928 KB	Output is correct
20	Correct	26 ms	23932 KB	Output is correct
21	Correct	22 ms	23936 KB	Output is correct
22	Correct	23 ms	23928 KB	Output is correct
23	Correct	21 ms	23936 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	23808 KB	Output is correct
29	Correct	21 ms	23808 KB	Output is correct
30	Correct	21 ms	23808 KB	Output is correct
31	Correct	21 ms	23800 KB	Output is correct
32	Correct	21 ms	23808 KB	Output is correct
33	Correct	22 ms	23808 KB	Output is correct
34	Correct	21 ms	23800 KB	Output is correct
35	Correct	21 ms	23808 KB	Output is correct
36	Correct	21 ms	23844 KB	Output is correct
37	Correct	21 ms	23808 KB	Output is correct
38	Correct	21 ms	23836 KB	Output is correct
39	Correct	22 ms	23804 KB	Output is correct
40	Correct	21 ms	23800 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	109 ms	35576 KB	Output is correct
2	Correct	146 ms	35616 KB	Output is correct
3	Correct	70 ms	31480 KB	Output is correct
4	Correct	32 ms	25464 KB	Output is correct
5	Correct	31 ms	24728 KB	Output is correct
6	Correct	41 ms	26360 KB	Output is correct
7	Correct	22 ms	23936 KB	Output is correct
8	Correct	66 ms	27796 KB	Output is correct
9	Correct	72 ms	29432 KB	Output is correct
10	Correct	22 ms	23936 KB	Output is correct
11	Correct	101 ms	31096 KB	Output is correct
12	Correct	108 ms	33272 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	22 ms	23808 KB	Output is correct
15	Correct	21 ms	23792 KB	Output is correct
16	Correct	21 ms	23808 KB	Output is correct
17	Correct	22 ms	23808 KB	Output is correct
18	Correct	24 ms	23808 KB	Output is correct
19	Correct	21 ms	23808 KB	Output is correct
20	Correct	21 ms	23808 KB	Output is correct
21	Correct	22 ms	23876 KB	Output is correct
22	Correct	21 ms	23808 KB	Output is correct
23	Correct	23 ms	23880 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	23808 KB	Output is correct
28	Incorrect	21 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #17152

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