Submission #844731

#	Time	Username	Problem	Language	Result	Execution time	Memory
844731		Mr_Husanboy	Race (IOI11_race)	C++17	100 / 100	1653 ms	42596 KiB

race

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

using namespace std;
#define ll long long
#define ff first
#define ss second

int d;

struct centroid{
    vector<vector<pair<int,int>>> g;
    vector<int> par, sz;
    vector<ll> dis;
    vector<bool> vis;
    multiset<pair<ll, int>> st;
    int n;

    centroid (int _n){
        init(_n);
    }

    void init(int _n){
        n = _n;
        g.assign(n, vector<pair<int,int>>());
        par.assign(n, 0);
        sz.assign(n, 0);
        vis.assign(n, false);
        dis.assign(n, 0ll);
    }

    void edge(int u, int v, int w){
        g[u].push_back({v, w}); 
        g[v].push_back({u, w});
    }

    int calc_size(int i, int p = -1){
        if(vis[i]) return 0;
        sz[i] = 1;
        for(auto [u, w] : g[i]){
            if(u == p) continue;
            sz[i] += calc_size(u, i);
        }
        //cout << i << ": " << sz[i] << ' ' << endl;
        return sz[i];
    }

    int find_centroid(int i, int p, int len){
        //cout << "i " << i << ' ';
        for(auto [u, w] : g[i]){
            if(vis[u] || u == p) continue;
            if(sz[u] > len/2) return find_centroid(u, i, len);
        }
        return i;
    }

    void decompose(int i = 0, int p = -1){
        int c = find_centroid(i, -1, calc_size(i));
        vis[c] = true;
        par[c] = p;
        //cout << c << endl;


        dfs(c, -1, 0, 0, 1);
        for(auto [u, w] : g[c]){
            if(vis[u]) continue;
            dfs(u, c, w, 1, -1);
            calc(u, c, w, 1);
            dfs(u, c, w, 1, 1);
        }
        dfs(c, -1, 0, 0, -1);
        
        for(auto [u, w] : g[c]){
            if(vis[u]) continue;
            decompose(u, c);
        }
    }

    int res = 1e9;
    void dfs(int i, int p, ll cur, int len, int flag){
        if(flag > 0){
          //cout << flag << endl;
          //cout << i << ' ' << cur << ' ' << len << endl;
            st.insert({cur, len});
        }else{
          //cout << flag << endl;
          //cout << i << ' ' << cur << ' ' << len << endl;
            st.erase(st.find({cur, len}));
        }
        for(auto [u, w] : g[i]){
            if(vis[u] || u == p) continue;
            dfs(u, i, cur + w, len + 1, flag);
        }
    }

    void calc(int i, int p, ll cur, int len){
        if(cur > d) return;
        auto it = st.lower_bound({d - cur, -1});
        if(it != st.end() && it->ff == d - cur){
           res = min(res, it->ss + len);
        }
        for(auto [u, w] : g[i]){
          if(vis[u] || u == p) continue;
          calc(u, i, cur + w, len + 1);
        }
    }
};


int best_path(int n, int k, int way[][2], int len[])
{
    
    d = k;
    centroid g(n);
    for(int i = 0; i < n - 1; i ++){
        g.edge(way[i][0], way[i][1], len[i]);
    }

    g.decompose();
    return g.res == 1e9 ? -1 : g.res;


}

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