oj.uz

Submission #485624

# Submission time Handle Problem Language Result Execution time Memory
485624 2021-11-08T15:34:55 Z Joo Dreaming (IOI13_dreaming) C++17
0 / 100
 45 ms 12356 KB 
#include <bits/stdc++.h>
#include "dreaming.h"
using namespace std;

const int MXN = 1e5+10;
using pi = pair<int,int>;

int best,mx[MXN][2],dps[MXN],dpp[MXN],fr[MXN];
bool vi[MXN];
vector<pi> G[MXN];

void dfs1(int u, int p){
    vi[u] = true;
    for(auto [v, w] : G[u]){
        if(v == p) continue;
        dfs1(v, u);
        dps[u] = max(dps[u], dps[v]+w);

        int tmp = dps[v]+w, node = v;
        if(tmp > mx[u][0]){
            swap(tmp, mx[u][0]);
            swap(fr[u], node);
        }
        if(tmp > mx[u][1]){
            swap(tmp, mx[u][1]);
        }
    }
}

void dfs2(int u, int p){
    best = min(best, max(dps[u], dpp[u]));
    for(auto [v, w] : G[u]){
        if(v == p) continue;

        if(v != fr[u]){
            dpp[v] = max(dpp[u], mx[u][0])+w;
        }else{
            dpp[v] = max(dpp[u], mx[u][1])+w;
        }

        dfs2(v, u);
    }
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
    int res[2] = {};
    for(int i = 0; i < M; i++){
        G[A[i]+1].emplace_back(B[i]+1, T[i]);
        G[B[i]+1].emplace_back(A[i]+1, T[i]);
    }

    int cmp = 0;
    for(int i = 1; i <= N; i++){
        if(!vi[i]){
            cmp++;
            best = 2e9;
            dfs1(i, 0);
            dfs2(i, 0);
            if(best > res[0]) swap(best, res[0]);
            if(best > res[1]) swap(best, res[1]);
        }
    }

    if(cmp <= 1) return 0;
    return res[0]+res[1]+L;
}

/*int main(void){
    int N,M,L;
    cin >> N >> M >> L;
    int A[M], B[M], T[M];
    for(int i = 0; i < M; i++){
        cin >> A[i];
    }
    for(int i = 0; i < M; i++){
        cin >> B[i];
    }
    for(int i = 0; i < M; i++){
        cin >> T[i];
    }
    cout << travelTime(N, M, L, A, B, T) << "\n";
    return 0;
}
*/

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 45 ms 12356 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 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 6792 KB Output is correct
2 Incorrect 20 ms 6940 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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