oj.uz

Submission #17151

# Submission time Handle Problem Language Result Execution time Memory
17151 2015-11-07T08:17:55 Z murat Dreaming (IOI13_dreaming) C++
14 / 100
 141 ms 35672 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -