oj.uz

Submission #153810

# Submission time Handle Problem Language Result Execution time Memory
153810 2019-09-16T14:18:51 Z popovicirobert Dreaming (IOI13_dreaming) C++14
14 / 100
 103 ms 13780 KB 
#include "dreaming.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
const int MAXN = (int) 1e5;

static vector < pair <int, int> > g[MAXN + 1];
static int dstA[MAXN + 1], dstB[MAXN + 1];
static bool vis[MAXN + 1], on_way[MAXN + 1];
static vector <int> nodes;

void dfs(int nod, int par, int *dst) {
    if(vis[nod] == 0) {
        nodes.push_back(nod);
    }
    vis[nod] = 1;
    for(auto it : g[nod]) {
        if(it.first != par) {
            dst[it.first] = dst[nod] + it.second;
            dfs(it.first, nod, dst);
        }
    }
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]) {
    int i;
    for(i = 0; i < m; i++) {
        A[i]++, B[i]++;
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }

    int nod = 0, dst = 0, ans = 0;
    for(i = 1; i <= n; i++) {
        if(vis[i]) continue;

        nodes.clear();
        dfs(i, 0, dstA);
        int a = 0;
        for(auto it : nodes) {
            if(dstA[it] >= dstA[a]) {
                a = it;
            }
        }
        dstA[a] = 0;
        dfs(a, 0, dstA);

        int b = 0;
        for(auto it : nodes) {
            if(dstA[it] >= dstA[b]) {
                b = it;
            }
        }
        dfs(b, 0, dstB);

        int cur_nod, cur_dst = INF;
        int id;

        for(auto it : nodes) {
            if(cur_dst >= max(dstA[it], dstB[it])) {
                cur_dst = max(dstA[it], dstB[it]);
                if(cur_dst == dstA[it]) {
                    id = a;
                }
                else {
                    id = b;
                }
                cur_nod = it;
            }
        }

        int aux = cur_nod;
        while(aux != id) {
            on_way[aux] = 1;
            for(auto it : g[aux]) {
                if(id == a) {
                    if(dstA[it.first] + it.second == dstA[aux]) {
                        aux = it.first;
                        break;
                    }
                }
                else {
                    if(dstB[it.first] + it.second == dstB[aux]) {
                        aux = it.first;
                        break;
                    }
                }
            }
        }
        on_way[id] = 1;

        if(ans < dstA[b] && (i == 1 || dstA[b] >= l + dst + cur_dst)) {
            ans = dstA[b];
            nod = cur_nod;
            dst = cur_dst;
        }
        else if(ans < l + dst + cur_dst) {
            ans = l + dst + cur_dst;
            cur_dst = dst + l;
            dst = max(dst, ans - dst);

            while(dst > max(cur_dst, ans - cur_dst)) {
                nod = cur_nod;
                dst = max(cur_dst, ans - cur_dst);
                for(auto it : g[nod]) {
                    if(on_way[it.first]) {
                        cur_nod = it.first;
                        cur_dst += it.second;
                        break;
                    }
                }
            }
        }

        /*cerr << ans << " " << dst << " " << nod << "\n";
        for(auto it : nodes) {
            cerr << it << " " << on_way[it] << "\n";
        }
        cerr << "\n";*/

    }
    return ans;
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:78:17: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
                 if(id == a) {
                 ^~
dreaming.cpp:92:20: warning: 'cur_nod' may be used uninitialized in this function [-Wmaybe-uninitialized]
         on_way[id] = 1;
         ~~~~~~~~~~~^~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13700 KB Output is correct
2 Correct 77 ms 13780 KB Output is correct
3 Correct 49 ms 9972 KB Output is correct
4 Correct 13 ms 4472 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 24 ms 5240 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 36 ms 6520 KB Output is correct
9 Correct 46 ms 8184 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 67 ms 9720 KB Output is correct
12 Correct 103 ms 11680 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13700 KB Output is correct
2 Correct 77 ms 13780 KB Output is correct
3 Correct 49 ms 9972 KB Output is correct
4 Correct 13 ms 4472 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 24 ms 5240 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 36 ms 6520 KB Output is correct
9 Correct 46 ms 8184 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 67 ms 9720 KB Output is correct
12 Correct 103 ms 11680 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 4 ms 2808 KB Output is correct
23 Correct 4 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 5 ms 2680 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2684 KB Output is correct
28 Incorrect 4 ms 2680 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13700 KB Output is correct
2 Correct 77 ms 13780 KB Output is correct
3 Correct 49 ms 9972 KB Output is correct
4 Correct 13 ms 4472 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 24 ms 5240 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 36 ms 6520 KB Output is correct
9 Correct 46 ms 8184 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 67 ms 9720 KB Output is correct
12 Correct 103 ms 11680 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 4 ms 2808 KB Output is correct
23 Correct 4 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 5 ms 2680 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2684 KB Output is correct
28 Incorrect 4 ms 2680 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 5964 KB Output is correct
2 Incorrect 33 ms 5880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13700 KB Output is correct
2 Correct 77 ms 13780 KB Output is correct
3 Correct 49 ms 9972 KB Output is correct
4 Correct 13 ms 4472 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 24 ms 5240 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 36 ms 6520 KB Output is correct
9 Correct 46 ms 8184 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 67 ms 9720 KB Output is correct
12 Correct 103 ms 11680 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 5 ms 2808 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 6 ms 2936 KB Output is correct
17 Correct 5 ms 2680 KB Output is correct
18 Correct 5 ms 2808 KB Output is correct
19 Correct 5 ms 2808 KB Output is correct
20 Correct 5 ms 2808 KB Output is correct
21 Incorrect 6 ms 2808 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 13700 KB Output is correct
2 Correct 77 ms 13780 KB Output is correct
3 Correct 49 ms 9972 KB Output is correct
4 Correct 13 ms 4472 KB Output is correct
5 Correct 12 ms 3576 KB Output is correct
6 Correct 24 ms 5240 KB Output is correct
7 Correct 4 ms 2680 KB Output is correct
8 Correct 36 ms 6520 KB Output is correct
9 Correct 46 ms 8184 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 67 ms 9720 KB Output is correct
12 Correct 103 ms 11680 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 4 ms 2680 KB Output is correct
15 Correct 4 ms 2680 KB Output is correct
16 Correct 4 ms 2680 KB Output is correct
17 Correct 4 ms 2680 KB Output is correct
18 Correct 4 ms 2680 KB Output is correct
19 Correct 4 ms 2680 KB Output is correct
20 Correct 4 ms 2680 KB Output is correct
21 Correct 4 ms 2680 KB Output is correct
22 Correct 4 ms 2808 KB Output is correct
23 Correct 4 ms 2680 KB Output is correct
24 Correct 4 ms 2680 KB Output is correct
25 Correct 5 ms 2680 KB Output is correct
26 Correct 4 ms 2680 KB Output is correct
27 Correct 4 ms 2684 KB Output is correct
28 Incorrect 4 ms 2680 KB Output isn't correct
29 Halted 0 ms 0 KB -