Submission #1263450

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263450		kl0989e	Dreaming (IOI13_dreaming)	C++20	100 / 100	45 ms	18248 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vl vector<ll>
#define pi pair<int, int>
#define pl pair<ll,ll>
#define all(x) (x).begin(),(x).end()

const int maxn=1e5+10;

vector<vector<pi>> graph(maxn);

vector<pi> dst1(maxn,{0,-1}),dst2(maxn,{0,-1});
vi seen(maxn,0);
int dia=0;
multiset<int> mx;

void dfs(int cur, int prev) {
    seen[cur]=1;
    for (auto [to,c]:graph[cur]) {
        if (to==prev) {
            continue;
        }
        dfs(to,cur);
        if (dst1[to].fi+c>dst1[cur].fi) {
            dst2[cur]=dst1[cur];
            dst1[cur]={dst1[to].fi+c,to};
        }
        else if (dst1[to].fi+c>dst2[cur].fi) {
            dst2[cur]={dst1[to].fi+c,to};
        }
    }
    dia=max(dia,dst1[cur].fi+dst2[cur].fi);
}

int dfs2(int cur, int prev) {
    int mn=dst1[cur].fi;
    for (auto [to,c]:graph[cur]) {
        if (to==prev) {
            continue;
        }
        int t;
        if (dst1[cur].se!=to) {
            t=dst1[cur].fi+c;
        }
        else {
            t=dst2[cur].fi+c;
        }
        if (t>dst1[to].fi) {
            dst2[to]=dst1[to];
            dst1[to]={t,cur};
        }
        else if (t>dst2[to].fi) {
            dst2[to]={t,cur};
        }
        mn=min(mn,dfs2(to,cur));
    }
    return mn;
}

int travelTime(int n, int m, int l, int a[], int b[], int t[]) {
    for (int i=0; i<m; i++) {
        graph[a[i]].pb({b[i],t[i]});
        graph[b[i]].pb({a[i],t[i]});
    }
    for (int i=0; i<n; i++) {
        if (!seen[i]) {
            dfs(i,i);
            mx.insert(dfs2(i,i));
            if (mx.size()>3) {
                mx.extract(mx.begin());
            }
        }
    }
    if (mx.size()==3) {
        dia=max(dia,*mx.begin()+*next(mx.begin())+2*l);
        dia=max(dia,*next(mx.begin())+*next(next(mx.begin()))+l);
    }
    else if (mx.size()==2) {
        dia=max(dia,*mx.begin()+*next(mx.begin())+l);
    }
    return dia;
}

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