제출 #941443

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
941443		Mike_Vu	경주 (Race) (IOI11_race)	C++14	0 / 100	2 ms	12888 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 = 2e5+5;
const int maxx = 1e9+7;

int n, k;
vector<pii> a[maxn];

bitset<maxn> del;
int child[maxn];
int sz, root;

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 (v == p || del[v]) continue;
        couchild(v, u);
        child[u] += child[v];
    }
//    cout << u << ' ' << child[u] << endl;
}
int centroid(int u, int p) {
    for (int i = 0 ;i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (v == p || del[v]) continue;
        if (child[v] >= (sz >> 1)) return centroid(v, u);
    }
    return u;
}

int h[maxn];
int dis[maxn];
int tk[1000007];
vector<pii> temp;
vector<int> undo;

void dfs(int u, int p) {
    if(dis[u] > k) return;
    temp.push_back({dis[u], h[u]});
    undo.push_back(dis[u]);
    if (tk[k-dis[u]] < maxx) {
        minimize(ans, h[u] + tk[k-dis[u]]);
    }
    for (int i = 0; i < (int)a[u].size(); i++) {
        int v = a[u][i].fi;
        if (v == p || del[v]) continue;
        int w = a[u][i].se;
        dis[v] = dis[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
    }
}

//void dfsr(int u, int p) {
//    tk[dis[u]] = maxx;
//    for (int i = 0; i < (int)a[u].size(); i++) {
//        int v = a[u][i].fi;
//        if (v == p || del[v]) continue;
//        int w = a[u][i].se;
//        if (dis[u] + w > k) continue;
//        dfsr(v, u);
//    }
//}

void solve(int u) {
    couchild(u, 0);
    sz = child[u];
    if (sz == 1) {
        del[u] = true;
        return;
    }
    root = centroid(u, 0);
    tk[0] = 0;
    h[root] = dis[root] = 0;
    for (int i = 0; i < (int)a[root].size(); i++) {
        int v = a[root][i].first, w = a[root][i].se;
        if (del[v]) continue;
        if (w > k) continue;
        dis[v] = dis[root] + w;
        h[v] = h[root]+1;
        dfs(v, root);
        for (int i = 0; i < (int)temp.size(); i++) {
            minimize(tk[temp[i].fi], temp[i].se);
        }
        temp.clear();
    }
    //dfs erase
//    dfsr(root, 0);
//vector undo
    for (int i = 0; i < (int)undo.size(); i++) {
        tk[undo[i]] = maxx;
    }
    undo.clear();
    del[root] = true;
    //solve sub
    for (int i = 0; i < (int)a[root].size(); i++) {
        int v = a[root][i].first;
        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 = 1; i < n; 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++) {
        tk[i] = maxx;
    }
    solve(1);
    return (ans >= maxx ? -1 : ans);
}

//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);
//}
/*
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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57