Submission #1312733

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312733		wangzhiyi33	Dreaming (IOI13_dreaming)	C++20	18 / 100	37 ms	15948 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
#define ii pair<long long ,long long>
#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];
int nd,jrk;

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

int brp[maxn+2];
vector<int>oo;

void cari(int cur,int par,int tot){
    vis[cur]=true;
    oo.pb(cur);
    brp[cur]=max(brp[cur],tot);
    for(auto x : adj[cur]){
        if(x.fir==par)continue;
        cari(x.fir,cur,tot+x.sec);
    }
}

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<long long>apa;

    for(int q=0;q<n;q++){
        if(vis[q])continue;
        nd=jrk=-1;
        dfs(q,-1,0);
        int awal=nd;
        nd=jrk=-1;
        dfs(awal,-1,0);
        int akh=nd;
        cari(awal,-1,0);
        oo.clear();
        cari(akh,-1,0);

        int hmm=1e9;
        for(auto x : oo){
            hmm=min(hmm,brp[x]);
            
        }
        apa.pb(hmm);
    }
    sort(apa.rbegin(),apa.rend());

    long long 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: 18 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23