Submission #485624

#	Time	Username	Problem	Language	Result	Execution time	Memory
485624		Joo	Dreaming (IOI13_dreaming)	C++17	0 / 100	45 ms	12356 KiB

dreaming

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23