Submission #1075823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075823		TheQuantiX	Dreaming (IOI13_dreaming)	C++17	18 / 100	37 ms	19540 KiB

dreaming

#include <bits/stdc++.h>
#include "dreaming.h"

using namespace std;
using ll = long long;

ll n, m, q, k, x, y, a, b, c, l;
vector< pair<ll, ll> > G[100000];
ll mx[100000], mxu[100000];
bool vis[100000];

void dfs(ll x, ll p) {
    mx[x] = 0;
    mxu[x] = 0;
    vis[x] = 1;
    for (auto i : G[x]) {
        if (i.first != p) {
            dfs(i.first, x);
            mx[x] = max(mx[x], mx[i.first] + i.second);
        }
    }
}

void dfsu(ll x, ll p) {
    vector< pair<ll, ll> > v;
    for (auto i : G[x]) {
        if (i.first != p) {
            v.push_back({mx[i.first] + i.second, i.first});
        }
    }
    sort(v.rbegin(), v.rend());
    for (auto i : G[x]) {
        if (i.first != p) {
            mxu[i.first] = mxu[x] + i.second;
            if (v.size() != 1) {
                if (v[0].second != i.first) {
                    mxu[i.first] = max(mxu[i.first], v[0].first + i.second);
                }
                else {
                    mxu[i.first] = max(mxu[i.first], v[1].first + i.second);
                }
            }
            dfsu(i.first, x);
        }
    }
    // cout << x << ' ' << mx[x] << ' ' << mxu[x] << '\n';
}

pair<ll, ll> dfsp(ll x, ll p) {
    pair<ll, ll> pr = {max(mx[x], mxu[x]), x};
    for (auto i : G[x]) {
        if (i.first != p) {
            pr = min(pr, dfsp(i.first, x));
        }
    }
    return pr;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    n = N;
    m = M;
    l = L;
    for (int i = 0; i < n; i++) {
        G[i].clear();
        vis[i] = 0;
    }
    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]});
    }
    vector< pair<int, int> > vp;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            dfs(i, -1);
            dfsu(i, -1);
            vp.push_back(dfsp(i, -1));
        }
    }
    // for (auto i : vp) {
    //     cout << i.first << ' ' << i.second << '\n';
    // }
    sort(vp.rbegin(), vp.rend());
    int ans = vp[0].first;
    if (vp.size() > 1) {
        ans = max(ans, vp[0].first + vp[1].first + L);
    }
    if (vp.size() > 2) {
        ans = max(ans, vp[1].first + vp[2].first + L * 2);
    }
    return ans;
}

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