Submission #557683

#	Time	Username	Problem	Language	Result	Execution time	Memory
557683		peteza	Race (IOI11_race)	C++14	100 / 100	456 ms	36248 KiB

race

#include <iostream>
#include <utility>
#include <vector>
#include <cassert>
using namespace std;
using pii = pair<int, int>;

const int mxn = 200005;
pii dist[1000005];
vector<pii> adj[mxn];
int SOL = 1000005, kk;
int sz[mxn];
int cent, d2 = 1, dep;
bool rem[mxn], fil;

int getsz(int cur, int p) {
    sz[cur] = 1;
    for(pii e:adj[cur])
        if(e.first != p && !rem[e.first])
            sz[cur] += getsz(e.first, cur);
    return sz[cur];
}

int getcent(int tgt, int cur, int p) {
    for(pii e:adj[cur])
        if(e.first != p && !rem[e.first] && sz[e.first] > tgt/2)
            return getcent(tgt, e.first, cur);
    return cur;
}

void sol(int cur, int p) {
    if(dep > kk) return ;
    if(fil) {
        if(dist[dep].first == cent)
            dist[dep].second = min(d2, dist[dep].second);
        else
            dist[dep] = {cent, d2};
    }
    else if(dist[kk-dep].first == cent) SOL = min(dist[kk-dep].second+d2, SOL);
    d2++;
    for(pii e:adj[cur]) 
        if(e.first != p && !rem[e.first])
        {
            dep += e.second;
            sol(e.first, cur);
            dep -= e.second;
        }
    d2--;
}

void decompose(int cur) {
    
    cent = getcent(getsz(cur, -1), cur, -1);
    rem[cent] = 1;
    dist[0] = {cent, 0};
    for(pii e:adj[cent]) {
        if(rem[e.first]) continue;
        dep = e.second;
        fil = 0; sol(e.first, cent);
        fil = 1; sol(e.first, cent);
    }

    //cout << SOL << ' ' << cent << '\n';
    for(pii e:adj[cent])
        if(!rem[e.first]) decompose(e.first);
}

int best_path(int N, int K, int H[][2], int L[]) {
    //assert(N <= 150'000);
    kk = K;
    fill(dist, dist+1000003, pii(-1, -1));
    for(int i=0;i<N-1;i++) {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    decompose(1);
    
    return (SOL > N ? -1 : SOL);
}

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