Submission #1164438

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164438		canhnam357	Dreaming (IOI13_dreaming)	C++20	100 / 100	48 ms	18248 KiB

dreaming

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

const int MAXN = 2e5 + 5;
int par[MAXN];
int find(int u)
{
    return u == par[u] ? u : par[u] = find(par[u]);
}
void join(int a, int b)
{
    par[find(a)] = find(b);
}
int travelTime(int n, int m, int l, int A[], int B[], int T[]) 
{
    iota(par, par + n, 0);
    vector<vector<pair<int, int>>> adj(n);
    for (int i = 0; i < m; i++)
    {
        int u = A[i];
        int v = B[i];
        int w = T[i];
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
        join(u, v);
    }
    vector<int> f(n), s(n), g(n);
    function<void(int, int)> down_dfs = [&](int u, int p)
    {
        for (auto v : adj[u])
        {
            if (v.first == p) continue;
            down_dfs(v.first, u);
            int k = f[v.first] + v.second;
            if (k > f[u])
            {
                s[u] = f[u];
                f[u] = k;
            }
            else if (k > s[u])
            {
                s[u] = k;
            }
        }
    };
    function<void(int, int)> up_dfs = [&](int u, int p)
    {
        for (auto v : adj[u])
        {
            if (v.first == p) continue;
            if (f[u] == f[v.first] + v.second)
            {
                g[v.first] = max(g[u], s[u]) + v.second;
            }
            else
            {
                g[v.first] = max(g[u], f[u]) + v.second;
            }
            up_dfs(v.first, u);
        }
    };
    vector<int> sz;
    for (int i = 0; i < n; i++)
    {
        if (i == find(i))
        {
            down_dfs(i, -1);
            up_dfs(i, -1);
        }
    }
    vector<int> mn(n, INT_MAX);
    for (int i = 0; i < n; i++)
    {
        int k = find(i);
        mn[k] = min(mn[k], max(f[i], g[i]));
    }
    for (int i = 0; i < n; i++)
    {
        if (i == find(i)) sz.push_back(mn[i]);
    }
    sort(sz.rbegin(), sz.rend());
    if (m + 1 == n)
    {
        int ans = 0;
        for (int i = 0; i < n; i++) ans = max(ans, max(s[i], g[i]) + f[i]);
        return ans;
    }
    else if (m + 2 == n)
    {
        int ans = 0;
        for (int i = 0; i < n; i++) ans = max(ans, max(s[i], g[i]) + f[i]);
        ans = max(ans, sz[0] + sz[1] + l);
        return ans;
    }
    else
    {
        int ans = 0;
        for (int i = 0; i < n; i++) ans = max(ans, max(s[i], g[i]) + f[i]);
        ans = max(ans, sz[0] + sz[1] + l);
        ans = max(ans, sz[1] + sz[2] + 2 * 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