제출 #502957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
502957		doowey	꿈 (IOI13_dreaming)	C++14	100 / 100	75 ms	16768 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)1e5 + 100;
vector<pii> T[N];


bool vis[N];
int mx[N];

void dfs(int u, int par){
    vis[u]=true;
    for(auto x : T[u]){
        if(x.fi == par) continue;
        dfs(x.fi, u);
        mx[u]=max(mx[u], mx[x.fi] + x.se);
    }
}

int Q;
int outp = 0;

void dfs1(int u, int par, int in){
    Q = min(Q, max(in, mx[u]));
    outp = max(outp, mx[u] + in);
    pii mx0 = mp(0,-1);
    pii mx1 = mp(0,-1);
    pii cur;
    for(auto x : T[u]){
        if(x.fi == par) continue;
        cur = mp(mx[x.fi] + x.se, x.fi);
        if(cur > mx0){
            mx1 = mx0;
            mx0 = cur;
        }
        else if(cur > mx1){
            mx1 = cur;
        }
    }
    int send;
    for(auto x : T[u]){
        if(x.fi == par) continue;
        send = in + x.se;
        if(x.fi != mx0.se) send = max(send, mx0.fi + x.se);
        if(x.fi != mx1.se) send = max(send, mx1.fi + x.se);
        dfs1(x.fi, u, send);
    }
}



int travelTime(int n, int m, int L, int A[], int B[], int C[]) {
    for(int i = 0; i < m ; i ++ ){
        T[A[i]].push_back(mp(B[i], C[i]));
        T[B[i]].push_back(mp(A[i], C[i]));
    }
    vector<int> G;
    for(int i = 0 ; i < n; i ++ ){
        if(vis[i]) continue;
        dfs(i, -1);
        Q = (int)2e9;
        dfs1(i, -1, 0);
        G.push_back(Q);
    }
    sort(G.begin(), G.end());
    reverse(G.begin(), G.end());
    if(G.size() > 1){
        outp = max(outp, G[0] + G[1] + L);
        if(G.size() > 2){
            outp = max(outp, G[1] + G[2] + L * 2);
        }
    }
    return outp;
}

• Subtask 1: 14 / 14
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23