Submission #557636

#	Time	Username	Problem	Language	Result	Execution time	Memory
557636		peteza	Race (IOI11_race)	C++14	43 / 100	3056 ms	37132 KiB

race

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int mxn = 200005;
pii dist[1000005];
vector<pii> adj[mxn];
int SOL = INT_MAX, kk;
int sz[mxn];
bool rem[mxn];

int getsz(int cur, int p = -1) {
    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 = -1) {
    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 cent, int cur, int p, bool fil, int dep, int d2 = 1) {
    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 SOL = (dist[kk-dep].first == cent ? min(dist[kk-dep].second+d2, SOL) : SOL);
    for(pii e:adj[cur]) 
        if(e.first != p && !rem[e.first])
            sol(cent, e.first, cur, fil, dep+e.second, d2+1);
}

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

    //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[]) {
    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();
    return (SOL > N ? -1 : SOL);
}

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