Submission #998357

#	Time	Username	Problem	Language	Result	Execution time	Memory
998357		MarwenElarbi	Race (IOI11_race)	C++17	100 / 100	1252 ms	64080 KiB

race

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
#define MAX_N 500000
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<pair<int,int>> adj[nax];
int sz[nax];
bool removed[nax];
set<pair<ll,int>> st[nax];
int ans=1e9;
int get_tree_size(int x,int p){
    sz[x]=1;
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        sz[x]+=get_tree_size(u.fi,x);
    }
    return sz[x];
}
int get_centroid(int x,int t_sz,int p){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        if(sz[u.fi]*2>t_sz){
            return get_centroid(u.fi,t_sz,x);
        }
    }
    return x;
}
void dfs(int x,int centroid,int p,pair<ll,int> cur){
    for(auto u:adj[x]){
        if(u.fi==p||removed[u.fi]) continue;
        cur.fi+=u.se;
        cur.se++;
        dfs(u.fi,centroid,x,cur);
        cur.fi-=u.se;
        cur.se--;
    }
    //cout <<x<<" "<<centroid<<" "<<cur.fi<<" "<<cur.se<<endl;
    st[centroid].insert(cur);
}
int n,k;
void build(int x){
    int centroid=get_centroid(x,get_tree_size(x,-1),-1);
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        dfs(u.fi,u.fi,centroid,make_pair(u.se,1));
    }
    multiset<pair<ll,int>> stt;
    stt.insert({0,0});
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        for(auto i:st[u.fi]){
            stt.insert(i);
        }
    }
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        for(auto i:st[u.fi]){
            stt.erase(stt.find(i));
        }
        for(auto i:st[u.fi]){
            if(stt.lower_bound(make_pair(k-i.fi,0))==stt.end()) continue;
            auto cur=*stt.lower_bound(make_pair(k-i.fi,0));
            if(cur.fi+i.fi==k) ans=min(ans,cur.se+i.se);
        }
        for(auto i:st[u.fi]){
            stt.insert(i);
        }
    }
    for (auto u:adj[centroid])
    {
        if(removed[u.fi]) continue;
        st[u.fi].clear();
    }
    removed[centroid]=true;
    for(auto u:adj[centroid]){
        if(removed[u.fi]) continue;
        build(u.fi);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    for (int i = 0; i < n-1; ++i)
    {
        adj[H[i][0]].pb({H[i][1],L[i]});
        adj[H[i][1]].pb({H[i][0],L[i]});
    }
    build(0);
    if(ans==1e9) return -1;
    else return ans;
}

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