Submission #476287

#	Time	Username	Problem	Language	Result	Execution time	Memory
476287		urosk	Race (IOI11_race)	C++14	100 / 100	1169 ms	47696 KiB

race

#include "race.h"
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define maxn 200005
vector<pll> g[maxn];
ll n,k,c;
bool vis[maxn];
ll ans = llinf;
ll dfs_siz(ll u,ll par){
    ll siz = 1;
    for(pll p : g[u]){
        ll v = p.fi;
        if(vis[v]||v==par) continue;
        siz+=dfs_siz(v,u);
    }
    return siz;
}
ll decomp(ll u,ll par,ll m){
    ll siz = 1;
    bool ok = 1;
    for(pll p : g[u]){
        ll v = p.fi;
        if(vis[v]||v==par) continue;
        ll e = decomp(v,u,m);
        if(e>m/2) ok = 0;
        siz+=e;
    }
    if(siz<m/2) ok = 0;
    if(ok) c = u;
    return siz;
}
void dfs(ll u,ll par,ll len,ll j){
    if(len==k) ans = min(ans,j);
    if(len>=k) return;
    for(pll p : g[u]){
        ll v = p.fi;
        ll w = p.sc;
        if(vis[v]||v==par) continue;
        dfs(v,u,len+w,j+1);
    }
}
map<ll,ll> cnt;
vector<pll> tmp;
void calc(ll u,ll par,ll len,ll j){
    if(len>k) return;
    if(cnt.find(k-len)!=cnt.end()) ans = min(ans,cnt[k-len]+j);
    tmp.pb({len,j});
    for(pll p : g[u]){
        ll v = p.fi;
        ll w = p.sc;
        if(vis[v]||v==par) continue;
        calc(v,u,len+w,j+1);
    }
}
void solve(ll u){
    decomp(u,u,dfs_siz(u,u));
    //cerr<<u<< " "<<c<<endl;
    dfs(c,c,0,0);
    vis[c] = 1;
    cnt.clear();
    for(pll p : g[c]){
        ll v = p.fi;
        ll w = p.sc;
        if(vis[v]) continue;
        calc(v,v,w,1);
        while(!tmp.empty()){
            ll id = tmp.back().fi;
            ll len = tmp.back().sc;
            tmp.popb();
            if(cnt.find(id)==cnt.end()) cnt[id] = len;
            else cnt[id] = min(cnt[id],len);
        }
    }
    ll r = c;
    for(pll p : g[r]){
        ll v = p.fi;
        if(vis[v]) continue;
        solve(v);
    }
}
int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    for(ll i = 1;i<=n-1;i++){
        ll x = H[i-1][0],y = H[i-1][1],w = L[i-1];
        x++;
        y++;
        g[x].pb({y,w});
        g[y].pb({x,w});
    }
    solve(1);
    if(ans==llinf) ans = -1;
    return ans;
}

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