제출 #767388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
767388		Ahmed57	꿈 (IOI13_dreaming)	C++17	100 / 100	59 ms	19404 KiB

dreaming

#include "dreaming.h"

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>> adj[100001];
long long lon[100001] ,vis[100001];
void dfs(int i){
    lon[i] = 0;
    vis[i] = 1;
    for(auto j:adj[i]){
        if(vis[j.first]==0){
            dfs(j.first);
            lon[i] = max(lon[j.first]+j.second,lon[i]);
        }
    }
}
long long pref[100001],suf[100001];
long long mi = 1e18 , ma = 1e18;
void reroot(int i,int pr,long long cnt){
    mi = min(mi,max(cnt,lon[i]));
    ma = max(ma,max(cnt,lon[i]));
    long long maa = cnt;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        pref[j.first] = maa;
        maa = max(maa,lon[j.first]+j.second);
    }
    reverse(adj[i].begin(),adj[i].end());
    maa = cnt;
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        suf[j.first] = maa;
        maa = max(maa,lon[j.first]+j.second);
    }
    reverse(adj[i].begin(),adj[i].end());
    for(auto j:adj[i]){
        if(j.first==pr)continue;
        reroot(j.first,i,max(pref[j.first],suf[j.first])+j.second);
    }
}
int travelTime(int N,int M,int L,int A[],int B[],int T[]){
    for(int i = 0;i<M;i++){
        adj[A[i]].push_back({B[i],T[i]});
        adj[B[i]].push_back({A[i],T[i]});
    }
    vector<long long> v;
    long long ans = 0;
    for(int i = 0;i<N;i++){
        if(vis[i])continue;
        dfs(i);
        mi = 1e18;
        ma = 0;
        reroot(i,0,0);
        v.push_back(mi);
        ans = max(ans,ma);
    }
    sort(v.begin(),v.end());
    reverse(v.begin(),v.end());
    if(v.size()>1)ans = max(ans,v[0]+v[1]+L);
    if(v.size()>2)ans = max(ans,v[1]+v[2]+2*L);
    return ans;
}
/*
int main(){
    int N = 12 , M = 8 , L = 2;
    int A[] = {0,8,2,5,5,1,1,10};
    int B[] = {8,2,7,11,1,3,9,6};
    int T[] = {4,2,4,3,7,1,5,3};
    cout<<travelTime(N,M,L,A,B,T)<<endl;
}
*/

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