Submission #307462

#	Time	Username	Problem	Language	Result	Execution time	Memory
307462		talant117408	Race (IOI11_race)	C++17	100 / 100	1259 ms	43384 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) (v).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

const int NN = 2e5+7;
vector <vector <pii>> graph(NN);
vector <int> dis(1e6+7, 2e9), dis2(1e6+7, 2e9);
vector <int> saizu(NN), vis(NN), par(NN), cnt(1e6+7);
int ans = 2e9, need;

void calculate(int v, int p, int dista, int val, int flag){
    if(dista > need) return;
    if(flag){
        cnt[dista]++;
        if(dis[dista] == 2e9){
            dis[dista] = val;
        }
        else if(dis[dista] >= val){
            dis2[dista] = dis[dista];
            dis[dista] = val;
        }
    }
    else{
        cnt[dista]--;
        if(dis[dista] == val){
            dis[dista] = dis2[dista];
            dis2[dista]  = 2e9;
        }
        else if(dis2[dista] == val){
            dis2[dista] = 2e9;
        }
    }
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p){
            calculate(to.first, v, dista+to.second, val+1, flag);
        }
    }
}

void solve(int v, int p, int dista, int val){
    if(dista > need) return;
    if(cnt[need-dista]){
        ans = min(ans, val+dis[need-dista]);
    }
    for(auto to : graph[v]){
        if(!vis[to.first] && to.first != p){
            solve(to.first, v, dista+to.second, val+1);
        }
    }
}

void find_size(int v, int p = -1){
    if(vis[v]) return;
    saizu[v] = 1;

    for(auto to : graph[v]){
        if(to.first != p && !vis[to.first]){
            find_size(to.first, v);
            saizu[v] += saizu[to.first];
        }
    }
}

int find_centroid(int v, int p, int n){
    for(auto to : graph[v]){
        if(to.first != p && !vis[to.first]){
            if(!vis[to.first] && saizu[to.first] > n/2){
                return find_centroid(to.first, v, n);
            }
        }
    }
    return v;
}

void init_centroid(int v = 0, int p = -1){
    find_size(v);
    
    int c = find_centroid(v, -1, saizu[v]);
    vis[c] = 1;
    par[c] = p;
    calculate(c, par[c], 0, 0, 1);
    if(cnt[need]){
        ans = min(ans, dis[need]);
    }
    for(auto to : graph[c]){
        if(!vis[to.first]){
            calculate(to.first, c, to.second, 1, 0);
            solve(to.first, c, to.second, 1);
            calculate(to.first, c, to.second, 1, 1);
        }
    }
    calculate(c, par[c], 0, 0, 0);
    
    for(auto to : graph[c]){
        if(!vis[to.first]){
            init_centroid(to.first, c);
        }
    }
    vis[c] = 0;
}

int best_path(int n, int k, int h[][2], int l[]){
    int i;
    need = k;
    for(i = 0; i < n-1; i++){
        graph[h[i][0]].pb(mp(h[i][1], l[i]));
        graph[h[i][1]].pb(mp(h[i][0], l[i]));
    }
    
    init_centroid();
    
    return ans == 2e9 ? -1 : ans;
}
/*
11 12
0 1 3
0 2 4
2 3 5 
3 4 4
4 5 6 
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2

4 3
0 1 1
1 2 2
1 3 4
2

3 3
0 1 1
1 2 1
-1
*/

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