Submission #1263332

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263332		aren_dance	Dreaming (IOI13_dreaming)	C++20	100 / 100	83 ms	43464 KiB

dreaming

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

using namespace std;
const int N = 3e5+1;
vector<pair<int, int>> g[N];
int dp[N];
int depth[N];
int mx[N];
bool vis[N];
int dp1[N];
int dp2[N];
int h[N];
vector<int> gag[N];
int o;
vector<pair<int,int>> hert;
void dfs2(int v,int p) {
    mx[v] = depth[v];
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        depth[i.first] = depth[v] + i.second;
        dfs2(i.first,v);
        mx[v] = max(mx[i.first], mx[v]);
    }
    dp[v] = mx[v] - depth[v];
    vector<int> mas;
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        mas.push_back(mx[i.first]);
    }
    if (mas.empty() || mas.size()==1) {
        return;
    }
    sort(mas.rbegin(), mas.rend());
    dp[v] = max(dp[v],mas[0] + mas[1] - 2*depth[v]);
}
int get() {
    for (int i = 0;i < o;++i) {
        dp[i] = 0;
        mx[i] = 0;
        depth[i] = 0;
    }
    dfs2(0,-1);
    int answ = 0;
    for (int i = 0;i < o;++i) {
        answ = max(answ, dp[i]);
    }
    return answ;
}
void dfs(int v,int comp) {
    vis[v] = 1;
    gag[comp].push_back(v);
    for (auto i : g[v]) {
        if (!vis[i.first]) {
            dfs(i.first, comp);
        }
    }
}
void dfs3(int v,int p) {
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        h[i.first] = h[v] + i.second;
        dfs3(i.first, v);
        dp1[v] = max(dp1[v],dp1[i.first]+i.second);
    }
}
void dfs4(int v, int p) {
    multiset<int, greater<int>> st;
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        dp2[i.first] = dp2[v] + i.second;
        st.insert(dp1[i.first]+i.second);
    }
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        auto j = st.find(dp1[i.first]+i.second);
        st.erase(j);
        if (!st.empty()) {
            dp2[i.first] = max(dp2[i.first], *st.begin() + i.second);
        }
        st.insert(dp1[i.first]+i.second);
    }
    for (auto i : g[v]) {
        if (i.first == p) {
            continue;
        }
        dfs4(i.first, v);
    }
}
int travelTime(int n, int m, int l,
    int a[], int b[], int t[]) {
    o = n;
    for (int i = 0;i < m;++i) {
        g[a[i]].push_back({ b[i], t[i] });
        g[b[i]].push_back({ a[i],t[i] });
    }
    int cnt = 0;
    for (int i = 0;i < n;++i) {
        if (!vis[i]) {
            dfs(i, cnt);
            ++cnt;
        }
    }
    vector<int> px(n + 1);
    int mn_id = 0;
    int ans = 0;
    for (int j = 0;j < cnt;++j) {
        dfs3(gag[j][0], -1);
        dfs4(gag[j][0],-1);
        int p1;
        int answ = 1e9;
        for (auto i : gag[j]) {
            int x = max(dp1[i], dp2[i]);
            if (x < answ) {
                answ = x;
                p1 = i;
            }
        }
        if (answ > ans) {
            ans = answ;
            mn_id = p1;
        }
        px[j] = p1;
    }
    for (int i = 0;i < cnt;++i) {
        if (px[i] != mn_id) {
            g[px[i]].push_back({ mn_id,l });
            g[mn_id].push_back({ px[i], l});
        }
    }
    return get();
}

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