Submission #1245158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245158		vux2code	Race (IOI11_race)	C++20	100 / 100	460 ms	31496 KiB

race

// The capital, vodka, the Soviet bear!
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
#define fi first
#define se second
void maxi (int &x, int y) {x = max (x, y);}
void mini (int &x, int y) {x = min (x, y);}

const ll maxN = 2e5 + 5, inf64 = 5e8, maxA = 1e6 + 5;

int N, K;
int H [maxN] [2];
int L [maxN];

int n, k, sz [maxN], f [maxA], ans;
bool del [maxN];
vector <int> vec;
vector <pii> adj [maxN];

int dfs (int x, int par) {
    sz [x] = 1;
    for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
        sz [x] += dfs (i. fi, x);
    }
    return sz [x];
}

int finCen (int x, int par, int cnt) {
    for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
        if (sz [i. fi] >= cnt / 2) return finCen (i. fi, x, cnt);
    }
    return x;
}

void get (int x, int par, int dis, int numNode) {
    if (k >= dis) mini (ans, f [k - dis] + numNode);
//    cerr << k - dis << ' ' << f [k - dis] + numNode << '\n';
    for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
        get (i. fi, x, dis + i. se, numNode + 1);
    }
}

void update (int x, int par, int dis, int numNode) {
    if (dis <= k) {
        mini (f [dis], numNode);
        //cerr << dis << ' ' << numNode << '\n';
        vec. push_back (dis);
    }
    for (pii i : adj [x]) if (!del [i. fi] && i. fi != par) {
        update (i. fi, x, dis + i. se, numNode + 1);
    }
}

void build (int x) {
    int cnt = dfs (x, -1);
    int cen = finCen (x, -1, cnt);
    del [cen] = 1;
    for (pll i : adj [cen]) if (!del [i. fi]) {
        get (i. fi, cen, i. se, 1);
        update (i. fi, cen, i. se, 1);
    }
    //cerr << cen << '\n';
//    for (int i = 0; i < 5; i ++) cerr << f [i] << ' ';
//    cerr << '\n';
    for (int i : vec) f [i] = inf64;
    vec. clear ();
    for (pii i : adj [cen]) if (!del [i. fi]) build (i. fi);
}

int best_path (int N, int K, int H [] [2], int L []) {
    n = N; k = K;
//    cerr << n << ' ' << k << '\n';
    for (int i = 0, u, v, w; i < n - 1; i ++) {
        u = H [i] [0];
        v = H [i] [1];
        w = L [i];
//        cerr << u << ' ' << v << ' ' << w << '\n';
        adj [u]. push_back ({v, w});
        adj [v]. push_back ({u, w});
    }
//    for (int i = 0; i < n; i ++) {
//        for (pll j : adj [i]) cerr << "(" << j. fi << ',' << j. se << "),";
//        cerr << '\n';
//    }
    ans = inf64;
    for (int i = 1; i < maxA; i ++) f [i] = inf64;
    f [0] = 0;
    build (0);
    if (ans >= inf64) return -1;
    return ans;
}

// int main () {
//     ios::sync_with_stdio (0);
//     cin. tie (0);
//     cout. tie (0);
//     #define task "untitled1"
//     if (fopen (task".inp", "r")) {
//         freopen (task".inp", "r", stdin);
//         freopen (task".out", "w", stdout);
//     }
//     cin >> N >> K;
//     for (int i = 0; i < N - 1; i ++) cin >> H [i] [0] >> H [i] [1];
//     for (int i = 0; i < N - 1; i ++) cin >> L [i];
// //    cerr << N << ' ' << K << '\n';
// //    for (int i = 0; i < N - 1; i ++) cerr << H [i] [0] << ' ' <<  H [i] [1] << '\n';
// //    for (int i = 0; i < N - 1; i ++) cerr << L [i] << ' ';
//     cout << best_path (N, K, H, L) << '\n';
// }

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