oj.uz

Submission #679216

# Submission time Handle Problem Language Result Execution time Memory
679216 2023-01-07T18:40:58 Z kusssso Dreaming (IOI13_dreaming) C++17
18 / 100
 42 ms 13900 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;
ll 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;
    vector<int> R;
    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;
                d[j] = pa[j] = 0;
            }
            Tree.clear();
            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];
            }
            int rad = max(d[x], d[v] - d[x]);
            R.push_back(rad);
            longest = max(longest, rad);
            
            for (auto &j : Tree) d[j] = pa[j] = 0;
            Tree.clear();
        }
    }
    sort(R.rbegin(), R.rend());
    if (R.size() > 1) {
        longest = max(longest, R[0] + L + R[1]);
        if (R.size() > 2) {
            longest = max(longest, L + R[1] + L + R[2]);
        }
    }
    return longest;
}

// signed main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
//     
    // cout << travelTime(12, 8, 2, {0,8,2,5,5,1,1,10}, {8,2,7,11,1,3,9,6}, {4,2,4,3,7,1,5,3});
//     
    // return 0;
// }

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 13900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 13900 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6488 KB Output is correct
2 Correct 19 ms 6996 KB Output is correct
3 Correct 25 ms 6884 KB Output is correct
4 Correct 20 ms 6992 KB Output is correct
5 Correct 19 ms 6884 KB Output is correct
6 Correct 21 ms 7368 KB Output is correct
7 Correct 20 ms 7120 KB Output is correct
8 Correct 21 ms 6880 KB Output is correct
9 Correct 19 ms 6876 KB Output is correct
10 Correct 20 ms 7116 KB Output is correct
11 Correct 1 ms 2644 KB Output is correct
12 Correct 6 ms 4560 KB Output is correct
13 Correct 6 ms 4588 KB Output is correct
14 Correct 8 ms 4452 KB Output is correct
15 Correct 6 ms 4432 KB Output is correct
16 Correct 5 ms 4432 KB Output is correct
17 Correct 6 ms 4428 KB Output is correct
18 Correct 6 ms 4584 KB Output is correct
19 Correct 6 ms 4432 KB Output is correct
20 Correct 2 ms 2644 KB Output is correct
21 Correct 2 ms 2668 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 6 ms 4432 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 13900 KB Output isn't correct
2 Halted 0 ms 0 KB -