Submission #434889

#	Time	Username	Problem	Language	Result	Execution time	Memory
434889		kevinxiehk	Dreaming (IOI13_dreaming)	C++17	47 / 100	1087 ms	15104 KiB

dreaming

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

vector<pair<int, int>> conn[100005];
bool vi[100005];
bool vi2[100005];
int par2[100005];
int dk2[100005];
vector<int> dia, hf;
int md, mdx;
void dfs(int now, int 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(int now, int 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(int 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';
    int an = md;
    int 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(int 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 return max(dia[0], hf[0] + hf[1] + l);
}

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