Submission #524793

#	Time	Username	Problem	Language	Result	Execution time	Memory
524793		XII	Race (IOI11_race)	C++17	0 / 100	1 ms	204 KiB

race

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
#define ALL(x) (x).begin(), (x).end()

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define FORU(i, a, b) for(int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)

#define IOS cin.tie(0)->sync_with_stdio(false);
#define PROB "IOI11_race"
//void Fi(){
//    if(fopen(PROB".inp", "r")){
//        freopen(PROB".inp", "r", stdin);
//        freopen(PROB".out", "w", stdout);
//    }
//}

const int INF = 1e9;
using pi = pair<int, int>;
vector<bool> vis;
vector<int> sz, mned, mark;
vector<vector<pi>> adj;
int lengthPath, ti, ans;

int dfs(int u, int p){
    sz[u] = 1;
    for(auto [w, v]: adj[u]) if(v != p && !vis[v]){
        sz[u] += dfs(v, u);
    }
    return sz[u];
}

int centroid(int u, int p, int n){
    for(auto [w, v]: adj[u]) if(v != p && !vis[v]){
        if(sz[v] > n / 2) return centroid(v, u, n);
    }
    return u;
}

stack<pi> tmp;
void dfs2(int u, int p, int dis, int edg){
    if(dis > lengthPath) return;

    if(mark[lengthPath - dis] == ti){
        ans = min(ans, edg + mark[lengthPath - dis]);
    }
    tmp.emplace(dis, edg);

    for(auto [w, v]: adj[u]) if(v != p && !vis[v]){
        dfs2(v, u, dis + w, edg + 1);
    }
}

void build(int u, int p){
    int c = centroid(u, p, dfs(u, p));

    mned[0] = 0;
    mark[0] = ++ti;

    for(auto [w, v]: adj[c]) if(!vis[v]){
        dfs2(v, c, w, 1);
        for(; !tmp.empty(); tmp.pop()){
            auto [dis, edg] = tmp.top();
            if(mark[dis] == ti){
                mned[dis] = min(mned[dis], edg);
            } else{
                mned[dis] = edg;
                mark[dis] = ti;
            }
        }
    }

    vis[c] = true;
    for(auto [w, v]: adj[c]) if(!vis[v]){
        build(v, c);
    }
}

int best_path(int n, int k, int h[][2], int l[]){
    sz.resize(n);
    adj.clear(); adj.resize(n);
    vis.assign(n, false);
    mned.resize(k + 1);
    mark.assign(k + 1, 0);
    ti = 0;
    lengthPath = k;
    ans = INF;
    FOR(i, 0, n - 1){
        adj[h[i][0]].eb(l[i], h[i][1]);
        adj[h[i][1]].eb(l[i], h[i][0]);
    }
    build(0, -1);
    return (ans == INF ? -1 : ans);
}

//const int N = 2e5 + 1;
//int n, k;
//int h[N][2], l[N];
//
//void enter(){
//    cin >> n >> k;
//    FOR(i, 0, n - 1) cin >> h[i][0] >> h[i][1];
//    FOR(i, 0, n - 1) cin >> l[i];
//}
//
//int main(){
//    IOS;
//    Fi();
//    enter();
//    cout << best_path(n, k, h, l);
//    return 0;
//}

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