oj.uz

Submission #679323

# Submission time Handle Problem Language Result Execution time Memory
679323 2023-01-08T03:28:18 Z kusssso Dreaming (IOI13_dreaming) C++17
14 / 100
 58 ms 14328 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
using ll = long long;
const int N = 1e5 + 5;
#define fi first
#define se second

vector<int> Tree;
int d[N];
bool used[N];
int pa[N];

vector<pair<int, int>> g[N];

void dfs (int u, int p) {
    Tree.push_back(u);
    used[u] = 1;
    pa[u] = p;
    for (auto& e : g[u]) {
        int v = e.fi;
        int w = e.se;
        if (v != p) {
            d[v] = d[u] + w;
            dfs(v, u);
        }
    }
}

// int travelTime (int n, int m, int L, vector<int> A, vector<int> B, vector<int> T) {
    
int travelTime (int n, int m, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < m; i++) {
        g[A[i]].push_back({B[i], T[i]});
        g[B[i]].push_back({A[i], T[i]});
    }
    int longest = 0;
    int mxrad = 0;
    int root = -1;
    vector<int> center;
    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            dfs(i, -1);
            int v = i;
            for (auto& j : Tree) if (d[j] > d[v]) v = j;
            Tree.clear();
            d[v] = 0;
            dfs(v, -1);
            for (auto &j : Tree) if (d[j] > d[v]) v = j;
            int u = v;
            int x = v;
            while (u != -1) {
                if (abs(2 * d[u] - d[v]) < abs(2 * d[x] - d[v])) {
                    x = u;
                }
                u = pa[u];
            }
            if (mxrad < max(d[x], d[v] - d[x])) {
                mxrad = max(d[x], d[v] - d[x]);
                root = x;
            }
            center.push_back(x);
            longest = max(longest, d[v]);
            Tree.clear();
        }
    }
    for (int i = 0; i < center.size(); i++) {
        if (center[i] != root) {
            g[root].push_back({center[i], L});
            g[center[i]].push_back({root, L});
        }
    }
    dfs(0, -1);
    int v = 0;
    for (auto &j : Tree) if (d[j] > d[v]) v = j;
    d[v] = 0;
    dfs(v, -1);
    for (auto &j : Tree) if (d[j] > d[v]) v = j;
    longest = max(longest, d[v]);

    return longest;
}

// signed main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
//     
    // int n, m, L;
    // cin >> n >> m >> L;
    // vector<int> A(m), B(m), T(m);
    // for (int i = 0; i < m; i++) cin >> A[i] >> B[i] >> T[i];
//     
    // cout << travelTime(n,m,L,A,B,T);
//     
    // return 0;
// }

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:67:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0; i < center.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14208 KB Output is correct
2 Correct 48 ms 14328 KB Output is correct
3 Correct 31 ms 10696 KB Output is correct
4 Correct 8 ms 4492 KB Output is correct
5 Correct 7 ms 3788 KB Output is correct
6 Correct 13 ms 5460 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 24 ms 6924 KB Output is correct
9 Correct 31 ms 8492 KB Output is correct
10 Correct 2 ms 2664 KB Output is correct
11 Correct 51 ms 10540 KB Output is correct
12 Correct 58 ms 13324 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2660 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Incorrect 2 ms 2644 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14208 KB Output is correct
2 Correct 48 ms 14328 KB Output is correct
3 Correct 31 ms 10696 KB Output is correct
4 Correct 8 ms 4492 KB Output is correct
5 Correct 7 ms 3788 KB Output is correct
6 Correct 13 ms 5460 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 24 ms 6924 KB Output is correct
9 Correct 31 ms 8492 KB Output is correct
10 Correct 2 ms 2664 KB Output is correct
11 Correct 51 ms 10540 KB Output is correct
12 Correct 58 ms 13324 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2660 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 1 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Incorrect 2 ms 2644 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8732 KB Output is correct
2 Correct 34 ms 8808 KB Output is correct
3 Correct 26 ms 8660 KB Output is correct
4 Correct 27 ms 8800 KB Output is correct
5 Correct 29 ms 8648 KB Output is correct
6 Correct 28 ms 9288 KB Output is correct
7 Correct 28 ms 8912 KB Output is correct
8 Correct 28 ms 8688 KB Output is correct
9 Correct 29 ms 8588 KB Output is correct
10 Correct 40 ms 8968 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 13 ms 9288 KB Output is correct
13 Correct 14 ms 9316 KB Output is correct
14 Correct 13 ms 9312 KB Output is correct
15 Correct 12 ms 9332 KB Output is correct
16 Correct 13 ms 9288 KB Output is correct
17 Correct 12 ms 9404 KB Output is correct
18 Correct 13 ms 9416 KB Output is correct
19 Correct 12 ms 9288 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Incorrect 1 ms 2660 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2664 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 1 ms 2644 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 2 ms 2644 KB Output is correct
8 Correct 2 ms 2660 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2644 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Incorrect 2 ms 2644 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14208 KB Output is correct
2 Correct 48 ms 14328 KB Output is correct
3 Correct 31 ms 10696 KB Output is correct
4 Correct 8 ms 4492 KB Output is correct
5 Correct 7 ms 3788 KB Output is correct
6 Correct 13 ms 5460 KB Output is correct
7 Correct 2 ms 2668 KB Output is correct
8 Correct 24 ms 6924 KB Output is correct
9 Correct 31 ms 8492 KB Output is correct
10 Correct 2 ms 2664 KB Output is correct
11 Correct 51 ms 10540 KB Output is correct
12 Correct 58 ms 13324 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2664 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct
17 Correct 1 ms 2644 KB Output is correct
18 Correct 2 ms 2644 KB Output is correct
19 Correct 2 ms 2644 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2660 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 2 ms 2644 KB Output is correct
24 Correct 1 ms 2644 KB Output is correct
25 Correct 2 ms 2644 KB Output is correct
26 Correct 2 ms 2644 KB Output is correct
27 Correct 2 ms 2644 KB Output is correct
28 Incorrect 2 ms 2644 KB Output isn't correct
29 Halted 0 ms 0 KB -