Submission #998601

#	Time	Username	Problem	Language	Result	Execution time	Memory
998601		amine_aroua	Race (IOI11_race)	C++17	100 / 100	216 ms	42556 KiB

race

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using namespace std;
#define pb push_back
#define nl '\n'
#define fore(i, y) for(int i = 0; i < y; i++)
#define forr(i, x, y) for(int i = x;i<=y;i++)
#define forn(i, y, x) for(int i = y; i >= x; i--)
const int MAX_N = 200010;
const int MAX_K = 1000010;
int k;
int res = MAX_N;
vector<pair<int ,int>> adj[MAX_N];
vector<int> minPath(MAX_K , MAX_N);
bool forbidden[MAX_N];
int sz[MAX_N];
int depth[MAX_N] , dist[MAX_N];
void dfsSZ(int x , int p)
{
    sz[x] = 1;
    for(auto [u,l]   : adj[x])
    {
        if(u == p || forbidden[u])
            continue;
        dfsSZ(u , x);
        sz[x]+=sz[u];
    }
}
int dfs_down(int x , int p , int n)
{
    for(auto [u , l] : adj[x])
    {
        if(u == p || forbidden[u])
            continue;
        if(sz[u] > n/2)
            return dfs_down(u , x , n);
    }
    return x;
}
vector<int> nodes;
void dfs_compute(int x , int p , int L)
{
    nodes.pb(x);
    depth[x] = depth[p] + 1;
    dist[x] = dist[p] + L;
    for(auto [u , l] : adj[x])
    {
        if(u == p || forbidden[u])
            continue;
        dfs_compute(u , x , l);
    }
}
void rec(int root)
{
    dfsSZ(root , -1);
    int n = sz[root];
    int centroid = dfs_down(root , -1 , n);
    depth[centroid] = dist[centroid] = 0;
    minPath[0] = 0;
    vector<int> reset;
    reset.pb(0);
    for(auto [child , l] : adj[centroid])
    {
        if(forbidden[child])
            continue;
        nodes.clear();
        dfs_compute(child , centroid , l);
        for(auto node : nodes)
        {
            if(dist[node] <= k)
                res = min(res , depth[node] + minPath[k - dist[node]]);
        }
        for(auto node : nodes)
        {
            if(dist[node] <= k)
            {
                reset.pb(dist[node]);
                minPath[dist[node]] = min(minPath[dist[node]] , depth[node]);
            }
        }
    }
    for(auto r : reset)
        minPath[r] = MAX_N;
    forbidden[centroid] = 1;
    for(auto [child , l] : adj[centroid])
    {
        if(forbidden[child])
            continue;
        rec(child);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    k = K;
    fore(i , N - 1)
    {
        adj[H[i][0]].pb({H[i][1] , L[i]});
        adj[H[i][1]].pb({H[i][0] , L[i]});
    }
    rec(0);
    return (res == MAX_N ? -1 : res);
}

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