Submission #1277447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277447		nhmktu	Race (IOI11_race)	C++17	0 / 100	7 ms	11336 KiB

race

#include <bits/stdc++.h>
#define ll long long
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define pi pair<int,int>
#define pii pair<int,pi>
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(a) (int) a.size()
#define endl '\n'
#define data "data"

using namespace std;
const ll linf = 1e18;
const int inf = 1e9;
const int MOD = 1e9 + 7, M = 3e5;
const int MX = 1e6;

void add(int &a, int b)
{
    a += b;
    if(a>=MOD)
        a-=MOD;
    if(a<0)
        a += MOD;
}

int modulo(int x)
{
    if(x<=1)
        return 1;
    return (MOD - MOD/x) * modulo(MOD/x) % MOD;
}

int mul(int a, int b)
{
    return (1ll *a%MOD * b%MOD) % MOD;
}

int ans = inf;
int n;
ll k;
int mn[MX+3];
int Sz[M];
bool iscent[M];
vector<pi> adj[M];

void dfs(int u, int p)
{
    Sz[u] = 1;
    FOR(i, 0, sz(adj[u]) -1)
    {
        int v = adj[u][i].fi;
        if(v == p || iscent[v]) continue;
        dfs(v, u);
        Sz[u] += Sz[v];
    }
}

int find_cent(int u, int tree_sz, int p)
{
    FOR(i, 0, sz(adj[u]) -1)
    {
        int v = adj[u][i].fi;
        if(v == p || iscent[v] || Sz[v] * 2 < tree_sz) continue;
        return find_cent(v, tree_sz, u);
    }
    return u;
}

void compute(int u, int dept, bool f, ll sum, int p)
{
    if(sum > k) return;
    if(f == 1)
    {
        if(mn[k - sum] != -1)
            ans = min(ans, mn[k - sum] + dept);
    }
    else
    {
        if(mn[sum] == -1) mn[sum] = dept;
        else mn[sum] = min(mn[sum], dept);
    }

    FOR(i, 0, sz(adj[u]) -1)
    {
        int v = adj[u][i].fi, w = adj[u][i].se;
        if(iscent[v] || v == p) continue;
        compute(v, dept + 1, f, sum + 1ll * w, u);
    }
}

void Erase(int u, int dept, ll sum, int p)
{
    if(sum > k) return;
    mn[sum] = -1;
    FOR(i, 0, sz(adj[u]) -1)
    {
        int v = adj[u][i].fi, w = adj[u][i].se;
        if(iscent[v] || v == p) continue;
        Erase(v, dept + 1, sum + 1ll * w, u);
    }
}

void build_cent(int u)
{
    dfs(u, -1);
    int cur = find_cent(u, Sz[u], u);
    iscent[cur] = 1;

    mn[0] = 0;
    FOR(i, 0, sz(adj[cur]) -1)
    {
        int v = adj[cur][i].fi, w = adj[cur][i].se;
        if(iscent[v]) continue;
        compute(v, 1, 1, 1ll * w, cur);
        compute(v, 1, 0, 1ll * w, cur);
    }

    FOR(i, 0, sz(adj[cur]) -1)
    {
        int v = adj[cur][i].fi, w = adj[cur][i].se;
        if(iscent[v]) continue;
        Erase(v, 1, 1ll * w, u);
    }

    FOR(i, 0, sz(adj[cur]) -1)
    {
        int v = adj[cur][i].fi;
        if(iscent[v]) continue;
        build_cent(v);
    }
}

void solve(void)
{
    memset(mn, -1, sizeof(mn));
    mn[0] = 0;
    build_cent(1);
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;

    FOR(i, 0, n - 2)
    {
        int u = H[i][0];
        int v = H[i][1];
        adj[u].pb({v, L[i]});
        adj[v].pb({u, L[i]});
    }

    solve();
    if(ans == inf) ans = -1;
    return ans;
}

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