Submission #1275513

#	Time	Username	Problem	Language	Result	Execution time	Memory
1275513		dl_nguyenducdung2k8	Race (IOI11_race)	C++20	0 / 100	165 ms	327680 KiB

race

#ifndef ONLINEJUDGE
#include "race.h"
#endif // ONLINEJUDGE


#include<bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

template<class X, class Y>bool maximize(X &x, const Y &y){if(x < y) return x = y, true; return false;}
template<class X, class Y>bool minimize(X &x, const Y &y){if(x > y) return x = y, true; return false;}

#define ll long long
#define fi first
#define se second
#define pb push_back
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
#define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
#define C make_pair
#define MASK(i) (1LL << (i))
#define TURN_ON(i, x) ((x) | MASK(i))
#define TURN_OFF(i, x) ((x) & ~MASK(i))
#define CNT(x) (__builtin_popcountll(x))
#define get_bit(i, x) ((x) & MASK(i))
#define REV(i, x) ((x) ^ MASK(i))

const ll mod = 1e9 + 7;
const ll INF = 1e9;
const int maxn = 1e5 + 5;
typedef pair<int, int> pi;
typedef pair<int, pair<int,int>> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pair<ll,ll>>pll;

const int MAXN = (int)1e3 + 5;

int NumVer, Weight;
ll dist[MAXN];
int high[MAXN], tin[MAXN], tout[MAXN], timeDFS, id[MAXN], heavy[MAXN], ans = +INF;
map<ll, int>cnt_best_path;
vector<pi>g[MAXN];

int DFS1(int u, int par){
    tin[u] = ++timeDFS;
    id[timeDFS] = u;
    int sz = 1, mx_sz = 0;
    for(pi x: g[u]){
        int v = x.fi, w = x.se;
        if(v != par){
            dist[v] = dist[u] + w;
            high[v] = high[u] + 1;
            int c_sz = DFS1(v, u);
            if(maximize(mx_sz, c_sz)) heavy[u] = v;
            sz += c_sz;
        }
    }
    tout[u] = timeDFS;
    return sz;
}
void add(int u){
    auto it = cnt_best_path.find(dist[u]);
    if(it == cnt_best_path.end()) cnt_best_path[dist[u]] = high[u];
    else minimize(it -> se, high[u]);
}
void DFS2(int u, int par, bool keep){
    for(pi x: g[u]){
        int v = x.fi;
        if(v != par && v != heavy[u]) DFS2(v, u, 0);
    }
    if(heavy[u] != -1) DFS2(heavy[u], u, 1);
    auto it = cnt_best_path.find(Weight + dist[u]);
    if(it != cnt_best_path.end()) minimize(ans, it -> se - high[u]);
    add(u);
    ll must = 1LL * Weight + 2LL * dist[u];
    for(pi x: g[u]){
        int v = x.fi;
        if(v != par && v != heavy[u]){
            FOR(i, tin[v], tout[v]){
                int vertical = id[i];
                it = cnt_best_path.find(must - dist[vertical]);
                if(it != cnt_best_path.end()) minimize(ans, it -> se + high[vertical] - 2 * high[u]);
            }
            FOR(i, tin[v], tout[v]) add(id[i]);
        }
    }
    if(keep == 0){
        cnt_best_path.clear();
    }
}
int best_path(int N, int K, int H[][2], int L[]){
    NumVer = N, Weight = K;
    FOR(i, 1, N - 1){
        int u = H[i][0], v = H[i][1], w = L[i];
        ++u, ++v;
        g[u].pb(C(v, w));
        g[v].pb(C(u, w));
    }
    memset(heavy, 0xff, sizeof(heavy));
    DFS1(1, -1);
    DFS2(1, -1, 0);
    return (ans == +INF ? -1 : ans);
}

#ifdef ONLINEJUDGE
int H[MAXN][2], L[MAXN];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int N, K;
    cin >> N >> K;
    FOR(i, 1, N - 1) cin >> H[i][0] >> H[i][1] >> L[i];
    cout << best_path(N, K, H, L);
    return 0;
}
#endif // ONLINEJUDGE

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