Submission #1004950

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004950		Gray	Dreaming (IOI13_dreaming)	C++17	100 / 100	76 ms	27236 KiB

dreaming

#include "dreaming.h"
#include <algorithm>
#include <ios>
#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<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);
        dp[u].push_back(dp[v][0]+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){
    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);
        }
    }
    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 main(){
//     ios_base::sync_with_stdio(0);
//     cin.tie(nullptr);
//     cin >> n;
//     A.resize(n);
//     for (ll i=0; i<n-1; i++){
//         ll u, v; cin >> u >> v;
//         u--; v--;
//         e.push_back({1, {u, v}});
//         A[u].push_back(i);
//         A[v].push_back(i);
//     }
//     dp.resize(n);
//     vis.resize(n);
//     cout << fout(0).ff<<ln;
// }

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);
        }
    }
    // for (ll i=0; i<n; i++){
    //     cout << i << ": ";
    //     for (auto ch:dp[i]){
    //         cout << ch << " ";
    //     }
    //     cout << ln;
    // }
    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: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 18 / 18
• Subtask 5: 12 / 12
• Subtask 6: 23 / 23