Submission #331256

#	Time	Username	Problem	Language	Result	Execution time	Memory
331256		smax	Dreaming (IOI13_dreaming)	C++17	100 / 100	129 ms	18796 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

int mx[100005], mx2[100005];
bool vis[100005];
vector<pair<int, int>> adj[100005];

int dfs1(int u, int p) {
    vis[u] = true;
    mx[u] = mx2[u] = 0;
    int ret = 0;
    for (auto [v, w] : adj[u])
        if (v != p) {
            ret = max(ret, dfs1(v, u));
            if (mx[v] + w >= mx[u]) {
                mx2[u] = mx[u];
                mx[u] = mx[v] + w;
            } else if (mx[v] + w > mx2[u]) {
                mx2[u] = mx[v] + w;
            }
        }
    return max(ret, mx[u] + mx2[u]);
}

int dfs2(int u, int p) {
    int ret = mx[u];
    for (auto [v, w] : adj[u])
        if (v != p) {
            int memo = mx[v], memo2 = mx2[v], nxt = (mx[v] + w == mx[u] ? mx2[u] : mx[u]) + w;
            if (nxt >= mx[v]) {
                mx2[v] = mx[v];
                mx[v] = nxt;
            } else if (nxt > mx2[v]) {
                mx2[v] = nxt;
            }
            ret = min(ret, dfs2(v, u));
            mx[v] = memo;
            mx2[v] = memo2;
        }
    return ret;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for (int i=0; i<N; i++) {
        vis[i] = false;
        adj[i].clear();
    }
    for (int i=0; i<M; i++) {
        adj[A[i]].emplace_back(B[i], T[i]);
        adj[B[i]].emplace_back(A[i], T[i]);
    }

    vector<pair<int, int>> comp;
    for (int i=0; i<N; i++)
        if (!vis[i]) {
            int d = dfs1(i, -1), mxD = dfs2(i, -1);
            comp.emplace_back(mxD, d);
        }
    sort(comp.rbegin(), comp.rend());

    int ret = comp[0].second, mxD = comp[0].first;
    for (int i=1; i<(int)comp.size(); i++) {
        ret = max({ret, comp[i].first + mxD + L, comp[i].second});
        mxD = max(mxD, comp[i].first + L);
    }
    return ret;
}

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