Submission #1004695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004695		Gray	Dreaming (IOI13_dreaming)	C++17	32 / 100	49 ms	21080 KiB

dreaming

#include "dreaming.h"
#include <algorithm>
#include <iostream>
#include <vector>

#define ll long long
#define ff first
#define ss second
#define ln "\n"

using namespace std;
vector<pair<ll, pair<ll, ll>>> e;
vector<vector<ll>> A;
vector<vector<ll>> dp;
vector<ll> stmp;
vector<bool> vis;
ll n, m, l;
void dfs(ll u, ll p){
    vis[u]=1;
    if (A[u].size()==1 and u!=p){
        dp[u] = {0};
    }
    for (auto i:A[u]){
        ll v = e[i].ss.ff^e[i].ss.ss^u;
        if (v==p) continue;
        dfs(v, u);
        for (auto ch:dp[v]){
            dp[u].push_back(ch+e[i].ff);
        }
    }
    sort(dp[u].rbegin(), dp[u].rend());
    while (dp[u].size()>2) dp[u].pop_back();
}
void dfs2(ll u, ll p, ll &diam, ll &big, ll pass){
    // cout << u << endl;
    dp[u].push_back(pass);
    sort(dp[u].rbegin(), dp[u].rend());
    while (dp[u].size()>2) dp[u].pop_back();
    for (auto i:A[u]){
        ll v = e[i].ss.ff^e[i].ss.ss^u;
        if (v==p) continue;
        if (dp[u][0]==dp[v][0]+e[i].ff){
            dfs2(v, u, diam, big, dp[u][1]+e[i].ff);
        }else{
            dfs2(v, u, diam, big, dp[u][0]+e[i].ff);
        }
    }
    // cout << u << " <> " << dp[u][0] << ln;
    if (dp[u].size()==1){
        diam=max(diam, dp[u][0]);
        big=0;
        return;
    }
    diam=max(diam, dp[u][0]+dp[u][1]);
    big=min(big, dp[u][0]);
}
pair<ll, ll> fout(ll mem){
    dfs(mem, mem);
    ll diam=0, big=2e18;
    dfs2(mem, mem, diam, big, 0);
    // cout << mem << " -> " << diam << " " << big << endl;
    return {diam, big};
}
int travelTime(int N, int M, int L, int U[], int V[], int W[]) {
    n=N; m=M; l=L;
    // cout << N << " " << M << " " << L << ln;return 0;
    e.resize(m);
    A.resize(n);
    dp.resize(n);
    vis.resize(n);
    // return 0;
    for (ll i=0; i<m; i++){
        A[U[i]].push_back(i);
        A[V[i]].push_back(i);
        e[i] = {W[i], {U[i], V[i]}};
    }
    ll ans=0;
    vector<ll> bigs;
    for (ll i=0; i<n; i++){
        // cout << i << ":";
        if (!vis[i]){
            // cout << i << endl;
            auto ret = fout(i);
            ans=max(ans, ret.ff);
            bigs.push_back(ret.ss);
        }
    }
    sort(bigs.rbegin(), bigs.rend());
    ans=max(ans, bigs[0]);
    if (bigs.size()>1){
        ans=max(ans, bigs[0]+bigs[1]+l);
    }
    if (bigs.size()>2){
        ans=max(ans, bigs[1]+bigs[2]+2*l);
    }
    return ans;
}

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