Submission #62162

#	Time	Username	Problem	Language	Result	Execution time	Memory
62162		reality	Race (IOI11_race)	C++17	100 / 100	1752 ms	67624 KiB

race

#include "race.h"
# include <bits/stdc++.h>
using namespace std;
# define x first
# define y second
# define ll long long
# define vi vector < int >
# define vl vector < ll >
# define pii pair < int , int >
# define mp make_pair
# define vii vector < pii >
# define pb push_back
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}

int best_path(int N, int K, int H[][2], int L[])
{
    static vii g[1 << 20];
    int n = N;
    for (int i = 0;i < n - 1;++i)
        g[H[i][0] + 1].pb(mp(H[i][1] + 1,L[i])),
        g[H[i][1] + 1].pb(mp(H[i][0] + 1,L[i]));
    int ans = 1e9;
    static int S[1 << 20];
    static int was[1 << 20];
    static int vv[1 << 20];
    static int D[1 << 20];
    for (int i = 1;i <= n;++i)
        was[i] = 1;
    for (int i = 1;i <= 1e6 + 5;++i)
        D[i] = -1;
    vi us;
    function < void(int,int) > dfs1 = [&](int node,int prev)
    {
        vv[node] = 0;
        us.pb(node);
        S[node] = 1;
        for (auto it : g[node])
            if (vv[it.x] && was[it.x])
                dfs1(it.x,node),S[node] += S[it.x];
    };
    vi vis;
    function < void(int,int,int,int) > dfs2 = [&](int node,int prev,int sum,int dep)
    {
        if (sum > K)
            return;
        vis.pb(sum);
        if (D[K - sum] != -1)
            smin(ans,D[K - sum] + dep);
        for (auto it : g[node])
            if (it.x != prev && was[it.x])
                dfs2(it.x,node,sum + it.y,dep + 1);
    };
    function < void(int,int,int,int) > dfs3 = [&](int node,int prev,int sum,int dep)
    {
        if (sum > K)
            return;
        if (D[sum] == -1 || D[sum] > dep)
            D[sum] = dep;
        for (auto it : g[node])
            if (it.x != prev && was[it.x])
                dfs3(it.x,node,sum + it.y,dep + 1);
    };
    while (*max_element(was + 1,was + 1 + n))
    {
        for (int i = 1;i <= n;++i)
            vv[i] = 1;
        for (int i = 1;i <= n;++i)
            if (vv[i] && was[i])
            {
                vis.clear();
                us.clear();
                dfs1(i,0);
                const int sz = us.size();
                pii mx = mp(n + 5,0);
                for (auto vertex : us)
                {
                    int mm = 0;
                    for (auto it : g[vertex])
                        if (was[it.x] && S[it.x] < S[vertex])
                            smax(mm,S[it.x]);
                    smax(mm,sz - S[vertex]);
                    smin(mx,mp(mm,vertex));
                }
                int vertex = mx.y;
                for (auto it : g[vertex])
                    if (was[it.x])
                    {
                        dfs2(it.x,vertex,it.y,1);
                        dfs3(it.x,vertex,it.y,1);
                    }
                was[vertex] = 0;
                for (auto it : vis)
                    D[it] = -1;
            }
    }
    if (ans == 1e9)
        ans = -1;
    return ans;
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57