Submission #434891

#	Time	Username	Problem	Language	Result	Execution time	Memory
434891		kevinxiehk	Dreaming (IOI13_dreaming)	C++17	100 / 100	101 ms	18028 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
#define ll long long
using namespace std;

vector<pair<ll, ll>> conn[100005];
bool vi[100005];
bool vi2[100005];
ll par2[100005];
ll dk2[100005];
vector<ll> dia, hf;
ll md, mdx;
void dfs(ll now, ll di) {
    if(vi[now]) return;
    vi[now] = true;
    if(di > md) {
        md = di;
        mdx = now;
    }
    for(auto x: conn[now]) dfs(x.fi, di + x.se);
}
void dfs2(ll now, ll di) {
    if(vi2[now]) return;
    vi2[now] = true;
    if(di > md) {
        md = di;
        mdx = now;
    }
    for(auto x: conn[now]) {
        if(!vi2[x.fi]){
            par2[x.fi] = now;
            dk2[x.fi] = x.se;
            dfs2(x.fi, di + x.se);
        }
    }
}
void once(ll a) {
    md = 0, mdx = a;
    dfs(a, 0);
    //cerr << a << ' ' << md << '\n';
    md = 0;
    par2[mdx] = -1;
    dfs2(mdx, 0);
    dia.pb(md);
   // cerr << a << ' ' << md << '\n';
    ll an = md;
    ll tt = md;

    while(mdx != -1) {
        an = min(an, max(md, tt - md));
        md -= dk2[mdx];
        mdx = par2[mdx];
    }
    //cerr << a << ' ' << an << '\n';

    hf.pb(an);
}
int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    
    for(ll i = 0; i < m; i++) {
        conn[a[i]].pb(mp(b[i], t[i]));
        conn[b[i]].pb(mp(a[i], t[i]));
    }
    for(int i = 0; i < n; i++) {
        if(vi[i]) continue;
        else once(i);
    }

    sort(dia.begin(), dia.end()); reverse(dia.begin(), dia.end());
    sort(hf.begin(), hf.end()); reverse(hf.begin(), hf.end());
    if(dia.size() == 1) return dia[0];
    else if(dia.size() == 2) return max(dia[0], hf[0] + hf[1] + l);
    else return max(dia[0], max(hf[0] + hf[1] + l, hf[1] + hf[2] + l * 2));
}

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