Submission #943163

#	Time	Username	Problem	Language	Result	Execution time	Memory
943163		Mike_Vu	Race (IOI11_race)	C++14	100 / 100	266 ms	67528 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double dou;
#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second

//const ll mod = 1e9+7;

bool maximize(ll &x, ll y ){
    if (x < y) {x = y; return true;};
    return false;
}
bool minimize(int &x, int y){
    if (x > y) {x = y; return true;}
    return false;
}
//void add(ll &x, ll y ){
//    x += y;
//    if (x >= mod) x -= mod;
//}
//void sub(ll &x, ll y) {
//    x -= y;
//    if (x < 0) x += mod;
//}

const int maxn = 1e6+5;
const int maxx = 1e9+7;

int n, k;
vector<pii> a[maxn];
bool del[maxn] = {0};
int child[maxn], target;
int ans = maxx;

void couchild(int u, int p) {
    child[u] = 1;
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (del[v] || v == p) continue;
        couchild(v, u);
        child[u] += child[v];
    }
}
int find_centroid(int u, int p) {
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v=  a[u][i].fi;
        if (del[v] || v == p) continue;
        if (child[v] * 2 > target) return find_centroid(v, u);
    }
    return u;
}

int h[maxn], dis[maxn], min_length[maxn];
vector<int> undo;
vector<pii> updates;
void dfs(int u, int p) {
    if (dis[u] > k) return;
    minimize(ans, h[u] + min_length[k-dis[u]]);
    updates.push_back(make_pair(dis[u], h[u]));
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].first;
        if (del[v] || v == p) continue;
        int w = a[u][i].se;
        dis[v] = dis[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}

void solve(int u) {
    couchild(u, -1);
    target = child[u];
    u = find_centroid(u, -1);
    del[u] = true;
    h[u] = dis[u] = 0;
    min_length[0] = 0;
    //solve
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (del[v]) continue;
        int w = a[u][i].se;
        dis[v] = w;
        h[v] = 1;
        dfs(v, u);
        //update
        for (int i = 0; i < (int)updates.size(); i++) {
            minimize(min_length[updates[i].fi], updates[i].se);
            undo.push_back(updates[i].fi);
        }
        updates.clear();
    }
    //clear
    for (int i = 0; i < (int)undo.size(); i++) {
        min_length[undo[i]] = maxx;
    }
    undo.clear();
    for (int i =0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (del[v]) continue;
        solve(v);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N;
    k = K;
    for (int i = 0; i < n-1; i++) {
        int u = H[i][0], v = H[i][1];
        int w = L[i];
        ++u;
        ++v;
        a[u].pb({v, w});
        a[v].pb({u, w});
    }
    for (int i = 1; i <= k; i++) {
        min_length[i] = maxx;
    }
    solve(1);
    return (ans >= maxx ? -1 : ans);
}

//#define Mike_Vui
#ifdef Mike_Vui
int N, K, H[maxn][2], L[maxn];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> K;
    for (int i = 1; i < N; i++) {
        cin >> H[i][0] >> H[i][1];
    }
    for (int i = 1; i < N; i++) {
        cin >> L[i];
    }
    cout <<  best_path(N, K, H, L);
}
#endif // Mike_Vui
/*
4 3
0 1
1 2
1 3
1
2
4
3 3
0 1
1 2
1
1
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3
4
5
4
6
3
2
5
6
7
*/

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