Submission #1088969

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088969		Tymond	Race (IOI11_race)	C++17	100 / 100	259 ms	43316 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
using ll = long long;
using ld = long double;
#define fi first
#define se second
#define vi vector<int>
#define vll vector<long long>
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

const int MAXN = 2e5 + 7;
vector<pii> g[MAXN];
bool blocked[MAXN];
int sz[MAXN];
int parent[MAXN];
int n, k;
ll ans;
ll m[1000010];
vector<pll> akt;

int dfs(int v, int p){
    sz[v] = 1;
    parent[v] = p;
    for(auto ele : g[v]){
        if(ele.fi == p || blocked[ele.fi]){
            continue;
        }
        sz[v] += dfs(ele.fi, v);
    }
    return sz[v];
}

void dfs2(int v, int p, pll s){
    if(s.fi > k){
        return;
    }
    akt.pb(s);
    for(auto ele : g[v]){
        if(blocked[ele.fi] || p == ele.fi || s.fi + ele.se > k){
            continue;
        }
        dfs2(ele.fi, v, {s.fi + ele.se, s.se + 1});
    }
}

void centroid_decomposition(int centroid){
    int roz = dfs(centroid, centroid);

    while(true){
        bool f = 0;
        for(auto ele : g[centroid]){
            if(ele.fi == parent[centroid] || blocked[ele.fi]){
                continue;
            }
            if(sz[ele.fi] * 2 >= roz){
                centroid = ele.fi;
                f = 1;
                break;
            }
        }
        if(!f){
            break;
        }
    }

    blocked[centroid] = 1;
    vector<pll> every;
    for(auto ele : g[centroid]){
        if(blocked[ele.fi]){
            continue;
        }
        akt.clear();
        dfs2(ele.fi, ele.fi, {ele.se, 1});
        for(auto ele2 : akt){
            every.pb(ele2);
            if(ele2.fi == k){
                ans = min(ans, ele2.se);
            }else if(ele2.fi < k){
                if(m[k - ele2.fi] != 0){
                    ans = min(ans, ele2.se + m[k - ele2.fi]);
                }
            }
        }

        for(auto ele2 : akt){
            if(m[ele2.fi] == 0){
                m[ele2.fi] = ele2.se;
            }else{
                m[ele2.fi] = min(m[ele2.fi], ele2.se);
            }
        }
    }
    for(auto ele : every){
        m[ele.fi] = 0;
    }

    for(auto ele : g[centroid]){
        if(blocked[ele.fi]){
            continue;
        }
        centroid_decomposition(ele.fi);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
    ans = 1e9;
    n = N;
    k = K;
    //cout << n << ' ' << k << '\n';
    for(int i = 0; i < n - 1; i++){
        //cout << H[i][0] << ' ' << H[i][1] << ' ' << L[i] << '\n';
        g[H[i][0]].pb({H[i][1], L[i]});
        g[H[i][1]].pb({H[i][0], L[i]});
    }

    centroid_decomposition(0);
    if(ans == (ll)1e9){
        return -1;
    }
    return (int)ans;
}

/*int main(){
    int tab[3][2] = {{0, 1}, {1, 2}, {1, 3}};
    int l[3] = {1, 2, 4};
    cout << best_path(4, 3, tab, l) << '\n';
    return 0;
}*/

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