Submission #1303431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303431		iamsazidh	Race (IOI11_race)	C++20	43 / 100	3096 ms	32840 KiB

race

#include "race.h"
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;

typedef long long              ll;
typedef double                 dl;
typedef vector<int>            vi;
typedef vector<vector<int>>    vii;
typedef vector<ll>             vl;
typedef vector<bool>           vb;
typedef pair<int,int>         pii;
typedef pair<ll, ll>          pll;

#define ff                first
#define ss                second
#define all(a)            a.begin(),a.end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          (a*(b/gcd(a,b)))
#define spc               " "

#ifdef ONLINE_JUDGE
    #define debarr(array)
    #define deb(x)
    #define del
#else
    #define debarr(array)  for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
    #define deb(x)         cerr << #x << " = " << x << endl;
    #define del cerr << '\n';
#endif


const double PI =         acos(-1);
const int MOD =           1000000007;
const int inf =           (2147483647);



int ans = inf;

class centroid_decomposition{
    private:
        vi dead, sub;
        vector<vector<pii>> adj;
        vector<int> mp;
        queue<int> que;
        queue<pii> add;
        int K;
    public:
        centroid_decomposition(int n, vector<vector<pii>> &_adj, int _K){
            adj = _adj;
            K = _K;
            dead.resize(n+1, 0);
            sub.resize(n+1);
            mp.resize(K+1000, n+1000);
            build(0);
        }
        void build(int u){
            int n = child(u);
            int cent = centroid(n, u);
            mp[0] = 0;
            dead[cent] = 1;
            for(auto v: adj[cent]){
                checkAns(v.ff, cent, v.ss, 1);
                while(!add.empty()){ mp[add.front().ff] = min(mp[add.front().ff], add.front().ss), que.push(add.front().ff), add.pop(); }
            }
            while(!que.empty()){
                mp[que.front()] = adj.size()+1000;
                que.pop();
            }
            for(auto v: adj[cent]){
                if(!dead[v.ff]) build(v.ff);
            }
            return;
        }
        void checkAns(int u, int p, int gone, int cnt){
            if(gone > K) return;
            int need = K-gone;
            if(need>=0 && need<mp.size()) ans = min(cnt+mp[need], ans);

            add.push({gone, cnt});

            for(auto x: adj[u])
                if(!dead[x.ff] && x.ff!=p) checkAns(x.ff, u, gone+x.ss, cnt+1);
            return;
        }
        int child(int u, int  p = -1){
            sub[u] = 1;
            for(auto v: adj[u])
                if(!dead[v.ff] && v.ff!=p) sub[u] += child(v.ff, u);
            return sub[u];
        }
        int centroid(int n, int u, int p = -1){
            for(auto v: adj[u])
                if(!dead[v.ff] && v.ff!=p && sub[v.ff]>n/2) return centroid(n, v.ff, u);
            return u;
        }
};

int best_path(int N, int K, int H[][2], int L[])
{
    ans = inf;
    vector<vector<pii>> adj(N+1);
    for(int i = 0; i < N-1; i++){
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    centroid_decomposition cd(N, adj, K);
    if(ans>N+100) return -1;
    return ans;


}

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