Submission #155848

#	Time	Username	Problem	Language	Result	Execution time	Memory
155848		TAISA_	꿈 (IOI13_dreaming)	C++14	100 / 100	347 ms	34652 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (1 << 30) - 1;
const ll LINF = (1LL << 60) - 1LL;
vector<vector<P>> G;
vector<int> dep, dp, vis;
vector<multiset<int>> st;
void build(int i, int p, int d) {
    vis[i] = 1;
    dep[i] = d;
    dp[i] = dep[i];
    for (auto &e : G[i]) {
        if (e.first == p) {
            continue;
        }
        build(e.first, i, d + e.second);
        dp[i] = max(dp[i], dp[e.first]);
        st[i].insert(dp[e.first] - dep[i]);
    }
}
pair<int, int> calc(int i, int p) {
    int res = INF, dia = 0;
    if (st[i].size() > 0) {
        auto itr = st[i].end();
        --itr;
        res = (*itr);
    }
    if (st[i].size() > 1) {
        auto itr = st[i].end();
        --itr;
        dia += (*itr);
        // cout << i << " " << (*itr) << endl;
        --itr;
        dia += (*itr);
        // cout << i << " " << (*itr) << endl;
    }
    for (auto &e : G[i]) {
        if (e.first == p) {
            continue;
        }
        int t = dp[e.first] - dep[i];
        st[i].erase(st[i].find(t));
        if (st[i].size() > 0) {
            auto it = st[i].end();
            --it;
            st[e.first].insert((*it) + e.second);
        } else {
            st[e.first].insert(e.second);
        }
        pair<int, int> re = calc(e.first, i);
        res = min(res, re.first);
        dia = max(dia, re.second);
        st[i].insert(t);
    }
    //  cout << i << " " << res << endl;
    return make_pair(res, dia);
}
int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    G.resize(N);
    st.resize(N);
    dep.resize(N);
    dp.resize(N);
    vis.resize(N);
    for (int i = 0; i < M; i++) {
        G[A[i]].push_back(P(B[i], T[i]));
        G[B[i]].push_back(P(A[i], T[i]));
    }
    vector<ll> s;
    ll ma = 0;
    for (int i = 0; i < N; i++) {
        if (!vis[i]) {
            if (G[i].size() == 0) {
                s.push_back(0);
                continue;
            }
            build(i, -1, 0);
            pair<int, int> re = calc(i, -1);
            ma = max(ma, (ll)re.second);
            //   cout << re.second << endl;
            s.push_back(re.first);
        }
    }
    sort(all(s));
    reverse(all(s));
    ll ans = ma;
    if (s.size() > 1) {
        ans = max(ans, s[0] + s[1] + L);
    }
    if (s.size() > 2) {
        ans = max(ans, s[1] + s[2] + 2LL * 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