Submission #1341335

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341335		tsengang	Dreaming (IOI13_dreaming)	C++20	0 / 100	33 ms	13596 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"
#define ll long long
#define pb push_back
#define ertunt return
using namespace std;
vector<pair<ll,ll>> adj[200005];
bool vis[200005];
ll mx;
void dfs(ll x,ll p,ll cur,ll &g){
    if(cur>mx){
        mx=cur;
        g=x;
    }
    for(auto [y,w]:adj[x]){
        if(y!=p) dfs(y,x,cur+w,g);
    }
}
int travelTime(int n,int m,int l,int a[],int b[],int t[]){
    for(ll i=0;i<m;i++){
        adj[a[i]].pb({b[i],t[i]});
        adj[b[i]].pb({a[i],t[i]});
    }
    vector<ll> rad;
    ll ans=0;
    for(ll i=0;i<n;i++){
        if(!vis[i]){
            ll g=i;
            mx=0;
            dfs(i,-1,0,g);
            ll h=g;
            mx=0;
            dfs(g,-1,0,h);
            ll diam=mx;
            ans=max(ans,diam);
            ll r=(diam+1)/2;
            rad.pb(r);
            queue<ll> q;
            q.push(i);
            vis[i]=1;
            while(!q.empty()){
                ll x=q.front(); q.pop();
                for(auto [y,_]:adj[x]){
                    if(!vis[y]){
                        vis[y]=1;
                        q.push(y);
                    }
                }
            }
        }
    }
    sort(rad.begin(),rad.end(),greater<ll>());
    if(rad.size()>=2)
        ans=max(ans,rad[0]+rad[1]+l);
    if(rad.size()>=3)
        ans=max(ans,rad[1]+rad[2]+2*l);
    ertunt ans;
}

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