Submission #720145

#	Time	Username	Problem	Language	Result	Execution time	Memory
720145		ooo	Race (IOI11_race)	C++14	100 / 100	559 ms	50092 KiB

race

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

using namespace std;
#define ll long long
const int nu = 3e5+5;
const int nuu = 1e6+6;
typedef pair<ll, ll> cap;
ll n, k, s[nu], f[nu], ans = 1e9, hh[nu], ms[nuu], pre[nuu];
bool r[nu];
vector< vector<cap> > g;
int dfs(int u, int t)
{
    s[u] = 1;
    for(cap x : g[u])
    {
        int v = x.first;
        if(r[v] || v == t) continue;
        s[u] += dfs(v, u);
    }
    return s[u];
}
int get_centroid(int u, int t, int sum)
{
    for(cap x : g[u])
    {
        int v = x.first;
        if(r[v] || v == t) continue;
        if(s[v]*2 > sum) return get_centroid(v, u, sum);
    }
    return u;
}
void dfs2(int u, int t, int w, int ok, int c)
{
    f[u] = f[t]+w; hh[u] = hh[t]+1;
    if(f[u] > k) return ;
    if(ok == 1)
    {
        if(pre[f[u]] != c) pre[f[u]] = c, ms[f[u]] = hh[u];
        else ms[f[u]] = min(ms[f[u]], hh[u]);
    }
    else
    {
        if(pre[k-f[u]] == c) ans = min(ans, hh[u]+ms[k-f[u]]);
    }
    for(cap x : g[u])
    {
        int v = x.first;
        ll l = x.second;
        if(v == t || r[v]) continue;
        dfs2(v, u, l, ok, c);
    }
}
void centroid(int u)
{
    int cnt = dfs(u, 0);
    int c = get_centroid(u, 0, cnt);
    r[c] = true;

    pre[0] = c; ms[0] = 0;
    for(cap x : g[c])
    {
        int v = x.first;
        ll l = x.second;
        if(r[v]) continue;
        dfs2(v, 0, l, 0, c); dfs2(v, 0, l, 1, c);
    }

    for(cap x : g[c])
    {
        int v = x.first;
        if(!r[v]) centroid(v);
    }
}
int best_path(int x, int y, int H[][2], int L[])
{
    n = x; k = y;
    g.resize(n+1);
    for(int i = 0; i < n-1; ++i)
    {
        ll u = H[i][0]; ll v = H[i][1]; ll c = L[i];
        u++; v++;
        g[u].push_back({v, c});
        g[v].push_back({u, c});
    }
    centroid(1);
    if(ans == 1e9) ans = -1;
    return ans;
}

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