제출 #452136

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
452136		FEDIKUS	꿈 (IOI13_dreaming)	C++17	47 / 100	110 ms	13980 KiB

dreaming

#include "dreaming.h"

#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define xx first
#define yy second

using namespace std;

typedef pair<int,int> pii;

const int maxn=1e5+10;

bool bio[maxn];
int dist[maxn];
int dp[maxn];
vector<pii> g[maxn];

void dfs1(int cvor){
    if(bio[cvor]) return;
    bio[cvor]=true;
    dp[cvor]=0;
    for(pii i:g[cvor]){
        if(bio[i.xx]) continue;
        dfs1(i.xx);
        dp[cvor]=max(dp[cvor],dp[i.xx]+i.yy);
    }
}

void uradi(int cvor,int prosli){
    dp[prosli]=dp[cvor]=0;
    for(auto i:g[prosli]){
        if(i.xx==cvor) continue;
        dp[prosli]=max(dp[prosli],dp[i.xx]+i.yy);
    }
    for(auto i:g[cvor]){
        dp[cvor]=max(dp[cvor],dp[i.xx]+i.yy);
    }
}

pii dfs2(int cvor,int prosli){
    if(prosli!=-1) uradi(cvor,prosli);
    pii ret={dp[cvor],cvor};
    for(pii i:g[cvor]){
        if(i.xx==prosli) continue;
        ret=min(ret,dfs2(i.xx,cvor));
    }
    if(prosli!=-1) uradi(prosli,cvor);
    return ret;
}

pii najd(int cvor,int prosli){
    pii ret=mp(0,cvor);
    for(pii i:g[cvor]){
        if(i.xx==prosli) continue;
        pii pom=najd(i.xx,cvor);
        pom.xx+=i.yy;
        ret=max(ret,pom);
    }
    return ret;
}

int odg(int cvor){
    return najd(najd(cvor,-1).yy,-1).xx;
}

int travelTime(int n,int m,int l,int a[],int b[],int t[]) {
    for(int i=0;i<n;i++) dist[i]=-1;
    for(int i=0;i<m;i++){
        g[a[i]].pb(mp(b[i],t[i]));
        g[b[i]].pb(mp(a[i],t[i]));
    }
    priority_queue<pii,vector<pii>,greater<pii> > pq;
    for(int i=0;i<n;i++){
        if(bio[i]) continue;
        dfs1(i);
        pq.push(dfs2(i,-1));
    }
    while(pq.size()!=1){
        pii t1,t2;
        t1=pq.top(); pq.pop();
        t2=pq.top(); pq.pop();
        g[t1.yy].pb(mp(t2.yy,l));
        g[t2.yy].pb(mp(t1.yy,l));
        if(max(t1.xx,t2.xx+l)<=max(t1.xx+l,t2.xx)) pq.push(mp(max(t1.xx,t2.xx+l),t1.yy));
        else pq.push(mp(max(t1.xx+l,t2.xx),t2.yy));
    }
    return odg(0);
}

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