Submission #819872

#	Time	Username	Problem	Language	Result	Execution time	Memory
819872		hungby04	Race (IOI11_race)	C++17	100 / 100	359 ms	49200 KiB

race

/// HuDzG
#include <bits/stdc++.h>
#define reset(a) memset(a,0,sizeof(a))
#define ll long long
#define ld long double
#define endl '\n'
#define AutoAC int main()
#define OO 1000000007
#define F first
#define S second
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pb push_back
#define mp make_pair
#define nmax 1000005
#define HUNGIT ""
#define MOD 1000000007

using namespace std;

int n, k;
vector <pii> adj[nmax];
int res = OO;
int cntChild[nmax], Min[nmax];
bool isCentroid[nmax];

int getCntChild(int u, int p)
{
    cntChild[u] = 1;
    for(pii v : adj[u])
        if(v.F != p && !isCentroid[v.F]) cntChild[u] += getCntChild(v.F, u);
    return cntChild[u];
}

int findCentroid(int u, int p, int Size)
{
    for(pii v : adj[u])
        if(v.F != p && !isCentroid[v.F] && cntChild[v.F] > Size) return findCentroid(v.F, u, Size);
    return u;
}

void dfs(int u, int p, bool isFill, int length, int depth)
{
    if(length > k) return;
    if(isFill) Min[length] = min(Min[length], depth);
    else res = min(res, depth + Min[k - length]);
    for(pii v : adj[u])
    {
        if(v.F != p && !isCentroid[v.F]) 
        {
            dfs(v.F, u, isFill, length + v.S, depth + 1);
        }
    }
}

void dfsReset(int u, int p, int length)
{
    if(length > k) return;
    Min[length] = OO;
    for(pii v : adj[u])
        if(v.F != p && !isCentroid[v.F]) dfsReset(v.F, u, length + v.S);
}

void decompose(int u)
{
    int centroid = findCentroid(u, 0, getCntChild(u, 0) >> 1);
    isCentroid[centroid] = 1;
    Min[0] = 0;
    for(pii v : adj[centroid])
        if(!isCentroid[v.F])
        {
            dfs(v.F, centroid, 0, v.S, 1);
            dfs(v.F, centroid, 1, v.S, 1);
        }
    dfsReset(centroid, 0, 0);
    for(pii v : adj[centroid])
        if(!isCentroid[v.F]) decompose(v.F);
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N; k = K;
    for(int i = 0; i < n - 1; i++)
    {
        int u = H[i][0], v = H[i][1], w = L[i];
        u++; v++;
        adj[u].pb(mp(v, w));
        adj[v].pb(mp(u, w));
    }
    fill(Min + 1, Min + 1 + k, OO);
    decompose(1);
    return (res == OO ? -1 : res);
}

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