제출 #231494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
231494		nickmet2004	꿈 (IOI13_dreaming)	C++11	0 / 100	63 ms	14968 KiB

dreaming

#include<bits/stdc++.h>
#include"dreaming.h"
#define f first
#define s second

using namespace std;

const int N = 2e5 + 500;
typedef pair<int, int> ipair;
int n , m , L;
vector<ipair> adj[N];
int dpD[N] , dpU[N];
bool vis[N];
vector<int> dist;

int MN = 2e9 + 5;
int mx1 = -1 , mx2 = -1;

void dfsU(int u , int p , int BOSS){
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(v == p) continue;
        if(u == BOSS){
            if(dpD[v] + w == mx1){
                if(mx2 == -1) dpU[v] = w;
                else dpU[v] = mx2 + w;
            } else dpU[v] = mx1 + w;
        }
        else dpU[v] = dpU[u] + w;
        dfsU(v , u , BOSS);
    }
    MN = min(MN , max(dpU[u] , dpD[u]));
}
void dfsD(int u , int BOSS){
    vis[u] = 1;
    for(ipair x : adj[u]){
        int v = x.f , w = x.s;
        if(vis[v]) continue;
        dfsD(v , BOSS);
        dpD[u] = max(dpD[u] , dpD[v] + w);
        if(u == BOSS){
            if(mx2 < dpD[v] + w){mx2 = dpD[v] + w; if(mx2 > mx1) swap(mx1 , mx2);}
        }
    }
    if(u == BOSS){ dfsU(u ,-1 , BOSS);}
}
int travelTime(int N , int M , int L , int A[] , int B[] , int C[]){
    n = N; m = M; L = L;
    for(int i = 0; i < m; ++i){
        adj[A[i]].emplace_back(B[i] , C[i]);
        adj[B[i]].emplace_back(A[i] , C[i]);
    }
    for(int i = 0; i < n; ++i){
        if(!vis[i]) {
            dfsD(i , i);
            dist.emplace_back(MN);
            //cerr << MN << " mn " << endl;
            MN = 2e9; mx1 = -1; mx2 = -1;
        }
    }
    sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    return max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
/*
int main (){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m >> L;
    for(int i = 0; i < m; ++i){
        int u , v , w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    for(int i = 0; i < n; ++i){
        if(!vis[i]) {
            dfsD(i , i);
            dist.emplace_back(MN);
            //cerr << MN << " mn " << endl;
            MN = 2e9; mx1 = -1; mx2 = -1;
        }
    }
    sort(dist.begin() , dist.end()); reverse(dist.begin() ,dist.end());
    cout << max(dist[0] + dist[1] + L , dist[1] + dist[2] + L + L);
}
*/

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