Submission #1312715

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312715		wangzhiyi33	꿈 (IOI13_dreaming)	C++20	0 / 100	29 ms	11180 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back
const int maxn=1e5;

vector<ii>adj[maxn+2];
bool vis[maxn+2];
ii mx[maxn+2];

void dfs(int cur,int par,int jrk){
    for(auto x : adj[cur]){
        if(x.fir==par)continue;
        dfs(x.fir,cur,jrk+x.sec);
        if(mx[x.fir].fir + x.sec>mx[cur].fir){
            mx[cur].sec=mx[cur].fir;
            mx[cur].fir=mx[x.fir].fir + x.sec;
        }
        else if(mx[x.fir].fir + x.sec>mx[cur].sec){
            mx[cur].sec=mx[x.fir].fir + x.sec;
        }
    }
}

int brp=1e9;

void reroot(int cur,int par,int jrk){
    vis[cur]=true;
    ii sblm=mx[cur];
    if(cur!=par){
        int baru=mx[par].fir+jrk;
        if(mx[par].fir-jrk==mx[cur].fir){
            baru=mx[par].sec+jrk;
        }

        if(mx[cur].fir<baru){
            mx[cur].sec=mx[cur].fir;
            mx[cur].fir=baru;
        }
        else if(mx[cur].sec<baru){
            mx[cur].sec=baru;
        }
    }
    brp=min(brp,mx[cur].fir);

    for(auto x : adj[cur]){
        if(x.fir==par)continue;
        reroot(x.fir,cur,x.sec);
    }
    mx[cur]=sblm;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for(int q=0;q<m;q++){
        adj[a[q]].pb({b[q],t[q]});
        adj[b[q]].pb({a[q],t[q]});
    }
    vector<int>apa;

    for(int q=0;q<m;q++){
        if(vis[q])continue;
        dfs(q,-1,0);
        brp=1e9;
        reroot(q,q,0);
        apa.pb(brp);
    }
    sort(apa.rbegin(),apa.rend());

    int ans=apa[0];
    if(apa.size()>1){
        ans=max(ans,apa[0]+apa[1]+l);
    }
    if(apa.size()>2){
        ans=max(ans,apa[2]+apa[1]+2*l);
    }

    return ans;
}

// signed main(){
//     int n,m,l;
//     cin>>n>>m>>l;
//     int a[n],b[n],t[n];
//     for(int q=0;q<m;q++){
//         cin>>a[q]>>b[q]>>t[q];
//     }
//     cout<<travelTime(n,m,l,a,b,t)<<endl;
// }

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