Submission #342258

#	Time	Username	Problem	Language	Result	Execution time	Memory
342258		richyrich	Race (IOI11_race)	C++17	9 / 100	597 ms	17516 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;
map<ll, ll> MG;
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);
        //printf("now at %d\n", x);
        for(auto c : M) {
            if(c.second.empty())continue;
            //printf("%d %d\n", c.first, (c.second.begin())->first);
        }
        if(!M[k + d[x]].empty()) {
            ans = min(ans, (M[k + d[x]].begin())->first - edges[x]);
            //printf("%d %d   %d %d\n", x, d[x] + k, (M[k + d[x]].rbegin())->first, edges[x], (M[k + d[x]].rbegin())->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 + d[x] - d[eul[i]] == 0) {
                    ans = min(ans, edges[eul[i]] - edges[x]);
                //    printf("here\n");
                }
                else if(!M[k + d[x] - d[eul[i]]].empty()) {
                    ll a = edges[eul[i]], b = (M[k + d[x] - d[eul[i]]].begin())->first;
                    ans = min(ans, a + b - edges[x]);
                //    printf("here\n");
                }
                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, 1, 0);
    /*for(int i = 0; i < n; i++) {
        for(int j = 0; j < i; j++) {
            if(d[i]-d[j] == 100)printf("here %d  %d %d\n", edges[i] - edges[j], i, j);
        }
    }
    for(int i = 0; i < n; i++) {
        printf("%d %d %d\n", i, d[i], edges[i]);
    }
    printf("%d\n", ans);
}
*/

Compilation message (stderr)

race.cpp:122:5: warning: "/*" within comment [-Wcomment]
  122 |     /*for(int i = 0; i < n; i++) {
      |

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