답안 #17155 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17155	2015-11-07T08:45:50 Z	murat	꿈 (IOI13_dreaming)	C++	14 / 100	141 ms	42704 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;

static int n, m, x, y, z, val[N], h[N];
static 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;
}

static 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);
}

static 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;

    for(int i = 0; i < N; i++)
        v[i].clear();

    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));
    }

    vector< pii > gg;

    memset(val, 0, sizeof val);
    memset(h, 0, sizeof h);

    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);
            gg.pb(mp(val[nnn], nnn));
        }
    }

    sort(gg.begin(), gg.end(), greater< pii >());

    for(int i = 1; i < gg.size(); i++) {
        v[gg[i].nd].pb(mp(gg[0].nd, L));
        v[gg[0].nd].pb(mp(gg[i].nd, L));
    }


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

    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:80:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < gg.size(); i++) {
                    ~~^~~~~~~~~~~
dreaming.cpp: At global scope:
dreaming.cpp:18:24: warning: 'z' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
                        ^
dreaming.cpp:18:21: warning: 'y' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
                     ^
dreaming.cpp:18:18: warning: 'x' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
                  ^
dreaming.cpp:18:15: warning: 'm' defined but not used [-Wunused-variable]
 static int n, m, x, y, z, val[N], h[N];
               ^

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	42616 KB	Output is correct
2	Correct	141 ms	42704 KB	Output is correct
3	Correct	80 ms	38952 KB	Output is correct
4	Correct	39 ms	33272 KB	Output is correct
5	Correct	37 ms	32504 KB	Output is correct
6	Correct	48 ms	34040 KB	Output is correct
7	Correct	29 ms	31688 KB	Output is correct
8	Correct	65 ms	35192 KB	Output is correct
9	Correct	78 ms	36984 KB	Output is correct
10	Correct	28 ms	31744 KB	Output is correct
11	Correct	115 ms	38500 KB	Output is correct
12	Correct	111 ms	40440 KB	Output is correct
13	Correct	28 ms	31736 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	42616 KB	Output is correct
2	Correct	141 ms	42704 KB	Output is correct
3	Correct	80 ms	38952 KB	Output is correct
4	Correct	39 ms	33272 KB	Output is correct
5	Correct	37 ms	32504 KB	Output is correct
6	Correct	48 ms	34040 KB	Output is correct
7	Correct	29 ms	31688 KB	Output is correct
8	Correct	65 ms	35192 KB	Output is correct
9	Correct	78 ms	36984 KB	Output is correct
10	Correct	28 ms	31744 KB	Output is correct
11	Correct	115 ms	38500 KB	Output is correct
12	Correct	111 ms	40440 KB	Output is correct
13	Correct	28 ms	31736 KB	Output is correct
14	Correct	27 ms	31616 KB	Output is correct
15	Correct	28 ms	31616 KB	Output is correct
16	Correct	29 ms	31608 KB	Output is correct
17	Correct	27 ms	31744 KB	Output is correct
18	Correct	27 ms	31616 KB	Output is correct
19	Correct	27 ms	31616 KB	Output is correct
20	Correct	27 ms	31608 KB	Output is correct
21	Correct	27 ms	31616 KB	Output is correct
22	Correct	29 ms	31616 KB	Output is correct
23	Correct	27 ms	31616 KB	Output is correct
24	Correct	33 ms	31740 KB	Output is correct
25	Correct	29 ms	31608 KB	Output is correct
26	Correct	29 ms	31608 KB	Output is correct
27	Correct	29 ms	31608 KB	Output is correct
28	Incorrect	27 ms	31616 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	42616 KB	Output is correct
2	Correct	141 ms	42704 KB	Output is correct
3	Correct	80 ms	38952 KB	Output is correct
4	Correct	39 ms	33272 KB	Output is correct
5	Correct	37 ms	32504 KB	Output is correct
6	Correct	48 ms	34040 KB	Output is correct
7	Correct	29 ms	31688 KB	Output is correct
8	Correct	65 ms	35192 KB	Output is correct
9	Correct	78 ms	36984 KB	Output is correct
10	Correct	28 ms	31744 KB	Output is correct
11	Correct	115 ms	38500 KB	Output is correct
12	Correct	111 ms	40440 KB	Output is correct
13	Correct	28 ms	31736 KB	Output is correct
14	Correct	27 ms	31616 KB	Output is correct
15	Correct	28 ms	31616 KB	Output is correct
16	Correct	29 ms	31608 KB	Output is correct
17	Correct	27 ms	31744 KB	Output is correct
18	Correct	27 ms	31616 KB	Output is correct
19	Correct	27 ms	31616 KB	Output is correct
20	Correct	27 ms	31608 KB	Output is correct
21	Correct	27 ms	31616 KB	Output is correct
22	Correct	29 ms	31616 KB	Output is correct
23	Correct	27 ms	31616 KB	Output is correct
24	Correct	33 ms	31740 KB	Output is correct
25	Correct	29 ms	31608 KB	Output is correct
26	Correct	29 ms	31608 KB	Output is correct
27	Correct	29 ms	31608 KB	Output is correct
28	Incorrect	27 ms	31616 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

Subtask #4
0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	72 ms	36040 KB	Output is correct
2	Correct	72 ms	35972 KB	Output is correct
3	Correct	71 ms	36008 KB	Output is correct
4	Correct	75 ms	36080 KB	Output is correct
5	Correct	72 ms	35876 KB	Output is correct
6	Correct	84 ms	36656 KB	Output is correct
7	Correct	73 ms	36088 KB	Output is correct
8	Correct	69 ms	35832 KB	Output is correct
9	Correct	72 ms	35768 KB	Output is correct
10	Correct	74 ms	36092 KB	Output is correct
11	Correct	28 ms	31616 KB	Output is correct
12	Correct	45 ms	36332 KB	Output is correct
13	Correct	65 ms	36332 KB	Output is correct
14	Correct	46 ms	36332 KB	Output is correct
15	Correct	45 ms	36460 KB	Output is correct
16	Correct	48 ms	36328 KB	Output is correct
17	Correct	46 ms	36332 KB	Output is correct
18	Correct	59 ms	36416 KB	Output is correct
19	Correct	46 ms	36332 KB	Output is correct
20	Correct	31 ms	31616 KB	Output is correct
21	Incorrect	28 ms	31624 KB	Output isn't correct
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	42616 KB	Output is correct
2	Correct	141 ms	42704 KB	Output is correct
3	Correct	80 ms	38952 KB	Output is correct
4	Correct	39 ms	33272 KB	Output is correct
5	Correct	37 ms	32504 KB	Output is correct
6	Correct	48 ms	34040 KB	Output is correct
7	Correct	29 ms	31688 KB	Output is correct
8	Correct	65 ms	35192 KB	Output is correct
9	Correct	78 ms	36984 KB	Output is correct
10	Correct	28 ms	31744 KB	Output is correct
11	Correct	115 ms	38500 KB	Output is correct
12	Correct	111 ms	40440 KB	Output is correct
13	Correct	28 ms	31736 KB	Output is correct
14	Correct	28 ms	31668 KB	Output is correct
15	Correct	28 ms	31744 KB	Output is correct
16	Correct	28 ms	31744 KB	Output is correct
17	Correct	30 ms	31608 KB	Output is correct
18	Correct	28 ms	31736 KB	Output is correct
19	Correct	29 ms	31744 KB	Output is correct
20	Correct	28 ms	31736 KB	Output is correct
21	Correct	31 ms	31876 KB	Output is correct
22	Correct	32 ms	31868 KB	Output is correct
23	Correct	30 ms	31616 KB	Output is correct
24	Correct	28 ms	31616 KB	Output is correct
25	Correct	29 ms	31608 KB	Output is correct
26	Correct	28 ms	31608 KB	Output is correct
27	Correct	29 ms	31608 KB	Output is correct
28	Correct	29 ms	31608 KB	Output is correct
29	Correct	28 ms	31608 KB	Output is correct
30	Correct	28 ms	31744 KB	Output is correct
31	Correct	27 ms	31608 KB	Output is correct
32	Correct	29 ms	31612 KB	Output is correct
33	Correct	28 ms	31608 KB	Output is correct
34	Correct	27 ms	31616 KB	Output is correct
35	Correct	27 ms	31616 KB	Output is correct
36	Correct	28 ms	31608 KB	Output is correct
37	Correct	28 ms	31780 KB	Output is correct
38	Correct	34 ms	31736 KB	Output is correct
39	Correct	27 ms	31608 KB	Output is correct
40	Correct	28 ms	31736 KB	Output is correct
41	Incorrect	28 ms	31608 KB	Output isn't correct
42	Halted	0 ms	0 KB	-

Subtask #6
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	121 ms	42616 KB	Output is correct
2	Correct	141 ms	42704 KB	Output is correct
3	Correct	80 ms	38952 KB	Output is correct
4	Correct	39 ms	33272 KB	Output is correct
5	Correct	37 ms	32504 KB	Output is correct
6	Correct	48 ms	34040 KB	Output is correct
7	Correct	29 ms	31688 KB	Output is correct
8	Correct	65 ms	35192 KB	Output is correct
9	Correct	78 ms	36984 KB	Output is correct
10	Correct	28 ms	31744 KB	Output is correct
11	Correct	115 ms	38500 KB	Output is correct
12	Correct	111 ms	40440 KB	Output is correct
13	Correct	28 ms	31736 KB	Output is correct
14	Correct	27 ms	31616 KB	Output is correct
15	Correct	28 ms	31616 KB	Output is correct
16	Correct	29 ms	31608 KB	Output is correct
17	Correct	27 ms	31744 KB	Output is correct
18	Correct	27 ms	31616 KB	Output is correct
19	Correct	27 ms	31616 KB	Output is correct
20	Correct	27 ms	31608 KB	Output is correct
21	Correct	27 ms	31616 KB	Output is correct
22	Correct	29 ms	31616 KB	Output is correct
23	Correct	27 ms	31616 KB	Output is correct
24	Correct	33 ms	31740 KB	Output is correct
25	Correct	29 ms	31608 KB	Output is correct
26	Correct	29 ms	31608 KB	Output is correct
27	Correct	29 ms	31608 KB	Output is correct
28	Incorrect	27 ms	31616 KB	Output isn't correct
29	Halted	0 ms	0 KB	-

답안 #17155

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