Submission #488279

#	Time	Username	Problem	Language	Result	Execution time	Memory
488279		SlavicG	Race (IOI11_race)	C++17	0 / 100	3 ms	4940 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long
 
#define       forn(i,n)              for(int i=0;i<n;i++)
#define          all(v)              v.begin(), v.end()
#define         rall(v)              v.rbegin(),v.rend()
 
#define            pb                push_back
#define          sz(a)               (int)a.size()

const int N = 2e5 + 10;
vector<pair<int, ll>> adj[N];
bool vis[N];
int s[N];
int K;
map<ll, int> dp;

void recalc(int u, int par){
    s[u] = 1;
    for(auto x: adj[u]){
        int v = x.first;
        if(v == par || vis[v])continue;
        recalc(v, u);
        s[u] += s[v];
    }
}

int find_centroid(int u, int need, int par){
    for(auto x: adj[u]){
        int v = x.first;
        if(v == par || vis[v])continue;
        if(s[v] > need)return find_centroid(v, need, u);
    }
    return u;
}
int ans = INT_MAX;

void dfs(int u, int par, ll weight, int type, int depth){ 
    if(type == 0){
        if(dp.count(K - weight)){
            ans = min(ans, dp[K - weight] + depth);
        }
    }
    else{
        if(!dp.count(weight))dp[weight] = depth;
        else dp[weight] = min(dp[weight], depth);
    }

    for(auto x: adj[u]){
        int v = x.first, w = x.second;

        if(v == par || vis[v])continue;
        dfs(v, u, weight + w, type, depth + 1);
    }
}

void centroid_decomp(int u){
    recalc(u, -1);
    int c = find_centroid(u, s[u] / 2, -1);
    vis[c] = true;
    dp.clear();
    dp[0] = 0;
    for(auto x: adj[c]){
        int v = x.first, w = x.second;
        if(vis[v])continue;
        dfs(v, -1, w, 0, 1);
        dfs(v, -1, w, 1, 1);
    }


    for(auto x: adj[c]){
        int v = x.first;
        if(vis[v])continue;
        centroid_decomp(v);
    }
}

int best_path(int n, int k, int h[][2],int l[]){
    ans = INT_MAX;
    for(int i = 0;i < n; ++i){
        adj[i].clear();
        vis[i] = 0;
    }
    dp.clear();
    for(int i = 0;i < n - 1; ++i){
        adj[h[i][0]].pb({h[i][1], l[i]});
        adj[h[i][1]].pb({h[i][0], l[i]});
    }

    centroid_decomp(0);
    if(ans == INT_MAX)return -1;
    return ans;
}
/*
void solve()
{ 
    int n, k;
    cin >> n >> k;
    K = k;
    vector<vector<int>> h(n - 1, vector<int>(2, 0));
    vector<int> l(n - 1);
    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];
    }

    cout << best_path(n, k, h, l) << "\n";

}   
 
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--)
    {
        solve();
    }
}
*/

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