Submission #953910

#	Time	Username	Problem	Language	Result	Execution time	Memory
953910		ArtieAaron	Race (IOI11_race)	C++14	0 / 100	2 ms	8796 KiB

race

#include <bits/stdc++.h> 
using namespace std;
typedef int lli;
typedef pair<lli, lli> ii;
typedef vector<lli> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
#define f first 
#define s second
#define pb push_back 
#define sz(v) (v).size()
#define all(v) sort((v).begin(), (v).end())
#define rall(v) sort((v).rbegin(), (v).rend())
#define SL '\n'
#define fore(a,s,d) for(lli a = (s), asd = (d); a < asd; a ++) 
#define wd(a,s) fore(a,0,s)
#define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const lli NN = 2e5;
lli vis[NN], rk[NN], curvis = 0;
lli n, k;
vii adj[NN];
bool err[NN];

lli dfs_rk(lli pos){
    // calcule los rangos desde una raíz random
    vis[pos] = curvis, rk[pos] = 1;
    for(auto i: adj[pos]){
        if(vis[i.f] == curvis or err[i.f]) continue;
        rk[pos] += dfs_rk(i.f);
    }
    return rk[pos];
}

lli dfs_cn(lli pos, lli x){
    // encuentre el centroide
    vis[pos] = curvis;
    ii mx = {-1e9, -1};
    for(auto i: adj[pos]){
        if(vis[i.f] == curvis or err[i.f]) continue;
        if(mx.f < rk[i.f]){
            mx.f = rk[i.f], mx.s = i.f;
        }
    }
    if(mx.f > x/2) return dfs_cn(mx.s, x);
    return pos;
}

void dfs_pa(lli pos, ii ans, vii &gans){
    // agrege las aristas mínimas para cada valor posible del sub-grafo
    // regresa peso, #aristas
    vis[pos] = curvis;
    for(auto i: adj[pos]){
        if(vis[i.f] == curvis or err[i.f]) continue;
        ii lans = ii({ans.f + i.f, ans.s + 1});
        gans.pb(lans);
        dfs_pa(i.f, lans, gans);
    }
    return;
}

lli cmna(vii v){
    // calcula el camino mas corto por iteración
    lli ans = 1e9;
    for(auto i: v){
        if(vis[i.f] == curvis) continue;
        lli pos = 1, s = lli(sz(v)) - 2;
        while(s){
            while(pos + s < lli(sz(v)) and v[pos + s].f <= k - i.f) pos += s;
            s /= 2;
        }
        if(v[pos].f + i.f == k){
            ans = min(ans, v[pos].s + i.s);
            vis[i.f] = vis[v[pos].f] = curvis;
        }
    }
    return ans;
}

lli best_path(lli N, lli K, lli H[][2], lli L[]){
    // re-escribir entrada
    {
        n = N, k = K;
        wd(i,n-1){
            adj[H[i][0]].pb(ii({H[i][1], L[i]}));
            adj[H[i][1]].pb(ii({H[i][0], L[i]}));
        }
    }
    lli ans = 1e9;
    queue<lli> q; q.push(0); err[0] = true;
    while(!q.empty()){
        lli o = q.front();
            q.pop();
        curvis = (curvis + 1) % lli(1e9);
        dfs_rk(o);
        curvis = (curvis + 1) % lli(1e9);
        lli cn = dfs_cn(o, rk[o]);
        // 3/2 * n
        curvis = (curvis + 1) % lli(1e9);
        vii paths = {};
        dfs_pa(cn, ii({0, 0}), paths);
        // + n
        all(paths);
        // + n log(n)
        vii spth = {};
        for(auto i: paths)
            if(sz(spth) == 0 or spth[lli(sz(spth))-1].f != i.f) spth.pb(i);
        err[cn] = true;
        curvis = (curvis + 1) % lli(1e9);
        lli mn = cmna(spth);
        // + n log(n)
        ans = min(ans, mn);
        for(auto i: adj[cn]){
            if(err[i.f]) continue;
            q.push(i.f);
        }
    }
    // + (push + insert) * n
    if(ans == 1e9) return -1;
    return ans;
}

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