Submission #342269

#	Time	Username	Problem	Language	Result	Execution time	Memory
342269		richyrich	Race (IOI11_race)	C++17	43 / 100	2276 ms	128236 KiB

race

//#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NMAX = 2e5+20;
const ll inf = 1e18;
ll n, eul[NMAX], siz[NMAX], in[NMAX], out[NMAX], edges[NMAX], timer, d[NMAX],ans,k;
vector<vector<pair<ll,ll>>> g(NMAX);
void dfs1(ll x, ll par) {
    siz[x] = 1;
    in[x] = timer;
    eul[timer++] = x;
    for(auto c : g[x]) {
        ll y = c.first;
        if(y==par) continue;
        edges[y] = edges[x] + 1;
        d[y] = d[x] + c.second;
        dfs1(y, x);
        siz[x] += siz[y];
    }
    out[x] = timer;
}
map<ll, map<ll,ll>> M;
void add(ll x, ll ancst) {
    M[d[x]][edges[x]]++;
}
void remove(ll x) {
    M[d[x]][edges[x]]--;
    if(M[d[x]][edges[x]] == 0) M[d[x]].erase(edges[x]);
    if(M[d[x]].empty())M.erase(d[x]);
    //printf("removing %d\n", x);
}
//ll check[NMAX];
void dfs2(ll x, ll p, bool keep, ll level) {
    ll mx = -1, bigc = -1;
    for(auto c : g[x]) {
        ll y = c.first;
        if(y == p) continue;
        if(siz[y] > mx) {
            mx = siz[y], bigc = y;
        }
    }
    for(auto c : g[x]) {
        ll y = c.first;    
        if(y != p && y != bigc) {
            dfs2(y,x,0,level+1);

        }
    }
    if(bigc != -1) {
        dfs2( bigc, x, 1, level+1);
        if(!M[k + d[x]].empty()) {
            ans = min(ans, (M[k + d[x]].begin())->first - edges[x]);
        }
    }
    for(auto c : g[x]) {
        ll y = c.first;
        if(y != p && y != bigc) {
            for(ll i = in[y]; i < out[y]; i++) {
                if(k + 2 * d[x] - d[eul[i]] == 0) {
                    ans = min(ans, edges[eul[i]] - edges[x]);
                }
                else if(!M[k + 2 * d[x] - d[eul[i]]].empty()) {
                    ll a = edges[eul[i]], b = (M[k + 2 * d[x] - d[eul[i]]].begin())->first;
                    ans = min(ans, a + b - 2 * edges[x]);
                }
                add(eul[i], x);
            }
        }
    }
    add(x, p);  
    if(!keep) {
        for(ll i = in[x]; i < out[x]; i++) {
            remove(eul[i]);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    ans = inf;
    k = K;
    for(ll i = 0; i < n-1; i++) {
        ll x = H[i][0], y = H[i][1];
        g[x].push_back({y, L[i]}), g[y].push_back({x, L[i]});
    }
    timer = 1;
    edges[0] = 0;
    dfs1(0, -1);
    dfs2(0, -1, 0, 0);
    if(ans == inf) ans = -1;
    return ans;
}
/*
int main() {
    ll N, K;
    cin >> N >> K;
    ll H[N][2], L[N];
    n = N;
    for(ll i = 0; i < N-1; i++) {
        cin >> H[i][0] >> H[i][1] >> L[i];
    }
    for(ll i = 0; i < N-1; i++) {
        ll x = H[i][0], y = H[i][1];
        g[x].push_back({y, L[i]}), g[y].push_back({x, L[i]});
    }
    timer = 1;
    edges[0] = 0;
    k = K;
    dfs1(0, -1);
    ans = inf;
    dfs2(0, -1, 0, 0);
    printf("%lld\n", ans);
}
*/

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