답안 #17151 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17151	2015-11-07T08:17:55 Z	murat	꿈 (IOI13_dreaming)	C++	14 / 100	141 ms	35672 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, vector< pii > , greater< 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	112 ms	35672 KB	Output is correct
2	Correct	102 ms	35596 KB	Output is correct
3	Correct	73 ms	31480 KB	Output is correct
4	Correct	31 ms	25592 KB	Output is correct
5	Correct	31 ms	24696 KB	Output is correct
6	Correct	39 ms	26368 KB	Output is correct
7	Correct	22 ms	23808 KB	Output is correct
8	Correct	60 ms	27896 KB	Output is correct
9	Correct	70 ms	29560 KB	Output is correct
10	Correct	22 ms	24064 KB	Output is correct
11	Correct	93 ms	31096 KB	Output is correct
12	Correct	141 ms	33268 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	35672 KB	Output is correct
2	Correct	102 ms	35596 KB	Output is correct
3	Correct	73 ms	31480 KB	Output is correct
4	Correct	31 ms	25592 KB	Output is correct
5	Correct	31 ms	24696 KB	Output is correct
6	Correct	39 ms	26368 KB	Output is correct
7	Correct	22 ms	23808 KB	Output is correct
8	Correct	60 ms	27896 KB	Output is correct
9	Correct	70 ms	29560 KB	Output is correct
10	Correct	22 ms	24064 KB	Output is correct
11	Correct	93 ms	31096 KB	Output is correct
12	Correct	141 ms	33268 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	23808 KB	Output is correct
16	Correct	22 ms	23808 KB	Output is correct
17	Correct	23 ms	23808 KB	Output is correct
18	Correct	25 ms	23808 KB	Output is correct
19	Correct	23 ms	23896 KB	Output is correct
20	Correct	22 ms	23808 KB	Output is correct
21	Correct	22 ms	23808 KB	Output is correct
22	Correct	25 ms	23800 KB	Output is correct
23	Correct	22 ms	23800 KB	Output is correct
24	Correct	57 ms	23800 KB	Output is correct
25	Correct	22 ms	23808 KB	Output is correct
26	Correct	22 ms	23808 KB	Output is correct
27	Correct	21 ms	23800 KB	Output is correct
28	Incorrect	22 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	35672 KB	Output is correct
2	Correct	102 ms	35596 KB	Output is correct
3	Correct	73 ms	31480 KB	Output is correct
4	Correct	31 ms	25592 KB	Output is correct
5	Correct	31 ms	24696 KB	Output is correct
6	Correct	39 ms	26368 KB	Output is correct
7	Correct	22 ms	23808 KB	Output is correct
8	Correct	60 ms	27896 KB	Output is correct
9	Correct	70 ms	29560 KB	Output is correct
10	Correct	22 ms	24064 KB	Output is correct
11	Correct	93 ms	31096 KB	Output is correct
12	Correct	141 ms	33268 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	23808 KB	Output is correct
16	Correct	22 ms	23808 KB	Output is correct
17	Correct	23 ms	23808 KB	Output is correct
18	Correct	25 ms	23808 KB	Output is correct
19	Correct	23 ms	23896 KB	Output is correct
20	Correct	22 ms	23808 KB	Output is correct
21	Correct	22 ms	23808 KB	Output is correct
22	Correct	25 ms	23800 KB	Output is correct
23	Correct	22 ms	23800 KB	Output is correct
24	Correct	57 ms	23800 KB	Output is correct
25	Correct	22 ms	23808 KB	Output is correct
26	Correct	22 ms	23808 KB	Output is correct
27	Correct	21 ms	23800 KB	Output is correct
28	Incorrect	22 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	86 ms	29880 KB	Output is correct
2	Incorrect	89 ms	29832 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	35672 KB	Output is correct
2	Correct	102 ms	35596 KB	Output is correct
3	Correct	73 ms	31480 KB	Output is correct
4	Correct	31 ms	25592 KB	Output is correct
5	Correct	31 ms	24696 KB	Output is correct
6	Correct	39 ms	26368 KB	Output is correct
7	Correct	22 ms	23808 KB	Output is correct
8	Correct	60 ms	27896 KB	Output is correct
9	Correct	70 ms	29560 KB	Output is correct
10	Correct	22 ms	24064 KB	Output is correct
11	Correct	93 ms	31096 KB	Output is correct
12	Correct	141 ms	33268 KB	Output is correct
13	Correct	22 ms	23936 KB	Output is correct
14	Correct	23 ms	23940 KB	Output is correct
15	Correct	24 ms	23936 KB	Output is correct
16	Correct	24 ms	23936 KB	Output is correct
17	Incorrect	22 ms	23936 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	112 ms	35672 KB	Output is correct
2	Correct	102 ms	35596 KB	Output is correct
3	Correct	73 ms	31480 KB	Output is correct
4	Correct	31 ms	25592 KB	Output is correct
5	Correct	31 ms	24696 KB	Output is correct
6	Correct	39 ms	26368 KB	Output is correct
7	Correct	22 ms	23808 KB	Output is correct
8	Correct	60 ms	27896 KB	Output is correct
9	Correct	70 ms	29560 KB	Output is correct
10	Correct	22 ms	24064 KB	Output is correct
11	Correct	93 ms	31096 KB	Output is correct
12	Correct	141 ms	33268 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	23808 KB	Output is correct
16	Correct	22 ms	23808 KB	Output is correct
17	Correct	23 ms	23808 KB	Output is correct
18	Correct	25 ms	23808 KB	Output is correct
19	Correct	23 ms	23896 KB	Output is correct
20	Correct	22 ms	23808 KB	Output is correct
21	Correct	22 ms	23808 KB	Output is correct
22	Correct	25 ms	23800 KB	Output is correct
23	Correct	22 ms	23800 KB	Output is correct
24	Correct	57 ms	23800 KB	Output is correct
25	Correct	22 ms	23808 KB	Output is correct
26	Correct	22 ms	23808 KB	Output is correct
27	Correct	21 ms	23800 KB	Output is correct
28	Incorrect	22 ms	23808 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #17151

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