Submission #1148696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148696		Tsagana	Dreaming (IOI13_dreaming)	C++20	0 / 100	12 ms	1600 KiB

dreaming

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

#define all(x) x.begin(), x.end()
#define lnl long long
#define pii pair<int, int>
#define pq priority_queue
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define F first
#define S second

using namespace std;

int P[10010], W[10010];
vector<pii> adj[10010];

pii dfs(int v, int p, int w)
{
    P[v] = p;
    W[v] = w;
    pii ans = {0, v};
    for (auto [u, w] : adj[v])
    {
        if (u == p) continue ;
        pii tmp = dfs(u, v, w);
        tmp.F += w;
        ans = max(ans, tmp);
    }
    return ans;
}

int travelTime(int N, int M, int L, int V[], int U[], int T[])
{
    for (int i = 0; i < M; i++)
    {
        adj[V[i]].pb({U[i], T[i]});
        adj[U[i]].pb({V[i], T[i]});
    }
    fill(P, P+N, -2);
    int ans = 0;
    vector<int> v;
    for (int i = 0; i < N; i++)
    {
        if (P[i] != -2) continue;
        int s = dfs(i, -1, 0).S;
        auto [x, u] = dfs(i, -1, 0);
        int y = 0;
        ans = max(ans, x);
        int k = 2e9;
        while (1)
        {
            k = min(k, max(x, y));
            if (P[u] == -1) break;
            y += W[u];
            x -= W[u];
            u = P[u];
        }
        v.pb(k);
    }
    sort(all(v));
    reverse(all(v));
    if (v.size() >= 2) ans = max(ans, L + v[0] + v[1]);
    if (v.size() >= 3) ans = max(ans, L + L + v[1] + v[2]);
    return ans;
}

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