Submission #342201

#	Time	Username	Problem	Language	Result	Execution time	Memory
342201		richyrich	Race (IOI11_race)	C++17	0 / 100	4 ms	5120 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll NMAX = 2e5+20;
const ll inf = 1e9;
int n, eul[NMAX], siz[NMAX], in[NMAX], out[NMAX], edges[NMAX], timer, d[NMAX],ans,k;
vector<vector<pair<int,int>>> g(NMAX);
void dfs1(int x, int par) {
    siz[x] = 1;
    in[x] = timer;
    eul[timer++] = x;
    for(auto c : g[x]) {
        int 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<int, map<int,int>> M;
map<int, int> MG;
void add(int x, int ancst) {
    M[d[x]][edges[x]]++;
}
void remove(int 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]);
}
//int check[NMAX];
void dfs2(int x, int p, bool keep, int level) {
    //check[level] = x;
    int mx = -1, bigc = -1;
    for(auto c : g[x]) {
        int y = c.first;
        if(y == p) continue;
        if(siz[y] > mx) {
            mx = siz[y], bigc = y;
        }
    }
    for(auto c : g[x]) {
        int 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]].rbegin())->first - edges[x]);
    }
    for(auto c : g[x]) {
        int y = c.first;
        if(y != p && y != bigc) {
            for(int i = in[y]; i < out[y]; i++) {
                if(k + d[x] - d[eul[i]] == 0) {
                    ans = min(ans, edges[eul[i]] - edges[x]);
                }
                else if(!M[k + d[x] - d[eul[i]]].empty()) {
                    int a = edges[eul[i]], b = (M[k + d[x] - d[eul[i]]].rbegin())->first;
                    ans = min(ans, a + b - edges[x]);
                }
                add(eul[i], x);
            }
        }
    }
    add(x, p);  
    if(!keep) {
        for(int 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(int i = 0; i < n-1; i++) {
        int 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);
    return ans == inf ? -1 : ans;
}

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