Submission #396764

#	Time	Username	Problem	Language	Result	Execution time	Memory
396764		IloveN	Race (IOI11_race)	C++14	100 / 100	1261 ms	62520 KiB

race

#include<bits/stdc++.h>

using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(vr) vr.begin(),vr.end()
#define vi vector<int>
#define vll vector<ll>
const int N = 2e5 + 10;

vector<pii> G[N];
int res, mark[N], sz[N], p[N];

void dfs_cen(int u, int r)
{
    sz[u] = 1;
    for (pii e : G[u])
        if (e.fi != r && !mark[e.fi]) p[e.fi] = u, dfs_cen(e.fi, u), sz[u] += sz[e.fi];
}

int h[N];
ll d[N];

void dfs(int u, int r, vi &vt)
{
    vt.eb(u);
    for (pii e : G[u])
        if (e.fi != r && !mark[e.fi])
        {
            h[e.fi] = h[u] + 1;
            d[e.fi] = d[u] + e.se;
            dfs(e.fi, u, vt);
        }
}

void build_centroid(vi &vt, int K)
{
    int len = vt.size();
    dfs_cen(vt[0], 0);
    int root = vt[0];
    for (int x : vt)
    {
        int mx = len - sz[x];
        for (pii e : G[x])
            if (!mark[e.fi] && e.fi != p[x]) mx = max(mx, sz[e.fi]);
        if (mx <= len / 2) root = x;
    }
    mark[root] = 1;
    vector<vi> vt_sub;
    map<ll,int> best;
    best[0] = 0;
    h[root] = 0;
    for (pii e : G[root])
    if (!mark[e.fi])
    {
        h[e.fi] = 1;
        d[e.fi] = e.se;
        vi s;
        dfs(e.fi, root, s);
        for (int x : s)
            if (d[x] <= K && best.count(K - d[x])) res = min(res, h[x] + best[K - d[x]]);
        for (int x : s)
            if (!best.count(d[x])) best[d[x]] = h[x];
            else best[d[x]] = min(best[d[x]], h[x]);
        vt_sub.eb(s);
    }
    for (vi s : vt_sub) build_centroid(s, K);
}

int best_path(int n, int K, int H[][2], int L[])
{
    for (int i = 1; i <= n; ++i) G[i].clear(), mark[i] = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        int u = H[i][0] + 1;
        int v = H[i][1] + 1;
        int w = L[i];
        G[u].eb(v,w);
        G[v].eb(u,w);
    }
    res = 1e9;
    vi vt;
    for (int i = 1; i <= n; ++i) vt.eb(i);
    build_centroid(vt, K);
    if (res == 1e9) res = -1;
    return res;
}

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