제출 #971785

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
971785		tnknguyen_	경주 (Race) (IOI11_race)	C++14	0 / 100	3 ms	13912 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define endl '\n' 
#define pii pair<int, int>
//#define int long long 

const int MX = 2e5 + 5;
const int MK = 1e6 + 5;

vector<pii> gr[MX];
vector<int> values;
int f[MK], vi[MK];
int sz[MX], del[MX];
int n, k, ans = 1e9;

int dfs(int u, int p){
    sz[u] = 1;
    for(pii e : gr[u]){
        int v = e.first;
        if(v != p && !del[v]){
            sz[u] += dfs(v, u);
        }
    }
    return sz[u];
}

int centroid(int u, int p, const int &n){
    for(pii e : gr[u]){
        int v = e.first;
        if(v != p && !del[v] && sz[v] > n/2){
            return centroid(v, u, n);
        }
    }
    return u;
}

void solve(int u, int p, int dep, int sum, int &ans, const int &op, const int &k){
    if(sum > k){
        return;
    }
    if(op == 1){
        ans = min(ans, dep + f[k - sum]);
    }
    else{
        f[sum] = min(f[sum], dep);
        values.push_back(sum);
    }

    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(v != p && !del[v]){
            solve(v, u, dep + 1, sum + c, ans, op, k);
        }
    }
}

void decompose(int u){
    dfs(u, 0);
    u = centroid(u, 0, sz[u]);
    del[u] = 1;
    vector<int> reset;

    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(!del[v]){
            values.clear();
            solve(v, u, 1, c, ans, 1, k);
            solve(v, u, 1, c, ans, 2, k);
            for(int x : values){
                if(vi[x] == 0){
                    vi[x] = 1;
                    reset.push_back(x);
                }
            }
        }
    }    

    for(int x : reset){
        f[x] = 1e9;
    }

    for(pii e : gr[u]){
        int v, c;
        tie(v, c) = e;
        if(!del[v]){
            decompose(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], c = L[i];
        ++u, ++v;
        gr[u].push_back({v, c});
        gr[v].push_back({u, c});
    }

    fill(f+1, f+K+1, 1e9);
    decompose(1);

    return (ans == 1e9 ? -1 : ans);
}

// int32_t main() {
//     ios_base::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);

//     freopen("main.inp","r",stdin);
//     freopen("main.out","w",stdout);

//     int n, k;
//     int h[20][2], l[20];
//     cin>>n>>k;
//     for(int i=0; i<n-1; ++i){
//         cin>>h[i][0]>>h[i][1]>>l[i];
//     }

//     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