oj.uz

Submission #833021

# Submission time Handle Problem Language Result Execution time Memory
833021 2023-08-21T19:39:07 Z SoulKnight Dreaming (IOI13_dreaming) C++17
0 / 100
 30 ms 12748 KB 
#include "dreaming.h"
// #include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <bitset>
#include <cstring>
#include <algorithm>

using namespace std;

#define ll long long
#define ln '\n'

const int N = 1e5 + 5;
const int INF = 1e9;


vector<pair<int, int>> adj[N];
int fir[N], sec[N], ans[N];

// int mn = INF, which = -1;
// vector<pair<int, int>> leader;

int mn = INF;
vector<int> leader;

void dfs1(int u, int p){
    for (auto& [e, v]: adj[u]){
        if (v == p) continue;
        dfs1(v, u);
        if (fir[v] + e > fir[u]){
            sec[u] = fir[u];
            fir[u] = fir[v] + e;
        } else if (fir[v] + e > sec[u]){
            sec[u] = fir[v] + e;
        }
    }
}

void dfs2(int u, int p, int to_p){
    ans[u] = max(to_p, fir[u]);
    // if (ans[u] < mn){
    //     mn = ans[u];
    //     which = u;
    // }
    mn = min(mn, ans[u]);

    for (auto& [e, v]: adj[u]){
        if (v == p) continue;
        if (fir[v] + e == fir[u]){
            dfs2(v, u, max(to_p, sec[u])+e);
        } else dfs2(v, u, ans[u]+e);
    }
}

void getLongestPath(int u){
    dfs1(u, -1);
    dfs2(u, -1, 0);
}

int travelTime(int NN, int M, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < M; i++){
        adj[A[i]].push_back({T[i], B[i]});
        adj[B[i]].push_back({T[i], A[i]});
    }
    memset(ans, -1, sizeof(ans));

    for (int i = 0; i < NN; i++){
        if (ans[i] != -1) continue;
        mn = INF;
        getLongestPath(i); // tree rooted at i
        // leader.push_back({mn, which});
        leader.push_back(mn);
    }


    // for (int i = 0; i < NN; i++){
    //     cout << ans[i] << ' ';
    // }
    // cout << ln;

    sort(leader.begin(), leader.end());
    int k = leader.size();

    if (k == 2) return leader[k-1] + leader[k-2] + L;
    else return max(leader[k-1] + leader[k-2] + L,
                    leader[k-2] + leader[k-3] + 2*L);
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 6892 KB Output is correct
2 Correct 14 ms 6868 KB Output is correct
3 Correct 13 ms 6900 KB Output is correct
4 Correct 13 ms 6900 KB Output is correct
5 Correct 15 ms 6868 KB Output is correct
6 Correct 14 ms 7320 KB Output is correct
7 Correct 15 ms 7012 KB Output is correct
8 Correct 14 ms 6744 KB Output is correct
9 Correct 13 ms 6816 KB Output is correct
10 Correct 14 ms 7016 KB Output is correct
11 Correct 2 ms 2968 KB Output is correct
12 Correct 4 ms 4176 KB Output is correct
13 Correct 4 ms 4300 KB Output is correct
14 Correct 5 ms 4176 KB Output is correct
15 Correct 4 ms 4300 KB Output is correct
16 Correct 4 ms 4176 KB Output is correct
17 Correct 4 ms 3920 KB Output is correct
18 Correct 4 ms 4300 KB Output is correct
19 Correct 4 ms 4176 KB Output is correct
20 Incorrect 2 ms 3028 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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