Submission #753993

#	Time	Username	Problem	Language	Result	Execution time	Memory
753993		phoenix0423	Race (IOI11_race)	C++17	100 / 100	1362 ms	47060 KiB

race

//centroid decomposition
//Submission : https://dmoj.ca/submission/5575237
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 2e5 + 5;
int n, k, ans = 1e9;

vector<pll> adj[maxn];
int L[maxn], vis[maxn], siz[maxn], H[maxn][2];
map<int, int> all, tmp;
// find centroid, calculate answer for centroid, remove the node and recurse for further centroids
void dfssz(int pos, int prev){
    siz[pos] = 1;
    for(auto [x, idx] : adj[pos]){
        if(x == prev || vis[x]) continue;
        dfssz(x, pos);
        siz[pos] += siz[x];
    }
}
void dfsans(int pos, int prev, int dis, int cnt){
    if(dis > k) return;
    if(tmp.find(dis) != tmp.end()) tmp[dis] = min(tmp[dis], cnt);
    else tmp[dis] = cnt;
    if(all.find(k - dis) != all.end()) ans = min(ans, cnt + all[k - dis]);
    for(auto [x, idx] : adj[pos]){
        if(x == prev || vis[x]) continue;
        dfsans(x, pos, dis + L[idx], cnt + 1);
    }
}
int get_centroid(int pos, int prev, int sz){
    for(auto [x, idx] : adj[pos]){
        if(x != prev && !vis[x] && siz[x] > sz / 2) return get_centroid(x, pos, sz);
    }
    return pos;
}
void centroid_decomposition(int pos){
    dfssz(pos, -1);
    int centroid = get_centroid(pos, -1, siz[pos]);
    vis[centroid] = 1;
    all.clear();
    all[0] = 0;
    for(auto [x, idx] : adj[centroid]){
        tmp.clear();
        if(vis[x]) continue;
        dfsans(x, -1, L[idx], 1);
        for(auto [dis, cnt] : tmp){
            if(all.find(k - dis) != all.end()) {
                ans = min(ans, cnt + all[k - dis]);
            }
        }
        for(auto [dis, cnt] : tmp){
            if(all.find(dis) != all.end()) all[dis] = min(all[dis], cnt);
            else all[dis] = cnt;
        }
    }
    for(auto [x, idx] : adj[centroid]){
        if(vis[x]) continue;
        centroid_decomposition(x);
    }
}
int best_path(int N, int K, int H[][2], int l[]){
    n = N, k = K;
    for(int i = 0; i < n - 1; i++){
        adj[H[i][0]].eb(H[i][1], i);
        adj[H[i][1]].eb(H[i][0], i);
    }
    for(int i = 0; i < n - 1; i++) L[i] = l[i]; 
    centroid_decomposition(0);
    return (ans < 1e9 ? ans : -1);  
}/*
void read_input(){
    cin>>n>>k;
    for(int i = 0; i < n - 1; i++) cin>>H[i][0]>>H[i][1]>>L[i];
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    read_input();
    ll ans = best_path(n, k, H, L);
    cout<<(ans > 1e7 ? -1 : ans)<<"\n";
}*/

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