Submission #261941

#	Time	Username	Problem	Language	Result	Execution time	Memory
261941		Falcon	Race (IOI11_race)	C++14	21 / 100	3075 ms	151032 KiB

race

// Needs constant (further) factor optimization.
#pragma GCC optimize("O2")

#include <bits/stdc++.h>
#ifdef DEBUG
    #include "debug.hpp"
#endif
#include <ext/pb_ds/assoc_container.hpp>

template<typename... args>
using hash_table = __gnu_pbds::cc_hash_table<args...> ;

using namespace std;

#define all(c) (c).begin(), (c).end()
#define traverse(c, it) for(auto it = (c).begin(); it != (c).end(); it++)
#define rep(i, N) for(int i = 0; i < (N); i++)
#define rep1(i, N) for(int i = 1; i <= (N); i++)
#define rep2(i, s, e) for(int i = (s); i <= (e); i++)
#define rep3(i, s, e, d) for(int i = (s); (d) >= 0 ? i <= (e) : i >= (e); i += (d))
#define pb push_back


#ifdef DEBUG
    #define debug(x...) {dbg::depth++; string dbg_vals = dbg::to_string(x); dbg::depth--; dbg::fprint(__func__, __LINE__, #x, dbg_vals);}
    #define light_debug(x) {dbg::light = 1; dbg::dout << __func__ << ":" << __LINE__ << "  " << #x << " = " << x << endl; dbg::light = 0;}
#else
    #define debug(x...)
    #define light_debug(x) 
#endif

template<typename T>
T& ckmin(T& a, T b){ return a = a > b ? b : a; }

template<typename T>
T& ckmax(T& a, T b){ return a = a < b ? b : a; }

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;

using Tree = vector<vector<pii>>;

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        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);
    }
};

struct CentroidDecompostion{
    vector<set<int>> adj;
    vi par, size;

    inline int init_size(int v, int p){
        debug(v);
        size[v] = 1;
        for(auto u : adj[v])
            if(u != p) size[v] += init_size(u, v);
        return size[v];
    }

    inline int centroid(int v, int p, int n){
        for(auto u : adj[v])
            if(u != p && size[u] > n / 2) 
                return centroid(u, v, n);
        return v;
    }

    int build(int v, int p){
        debug(v);
        init_size(v, p);
        int c = centroid(v, p, size[v]);
        par[c] = p;
        for(auto u : adj[c])
            adj[u].erase(c), build(u, c);
        adj[c].clear();
        return c;
    }

public:
    int operator()(Tree& _adj){
        debug(string("building centroid tree"))
        int n = _adj.size();
        adj.resize(n), size.resize(n), par.resize(n);
        rep(i, n)
            for(auto j : _adj[i])
                adj[i].insert(j.first);
        int r = build(0, -1);
        return r;
    }

    inline int operator [](int v){
        return par[v];
    }
};


struct TreeDist{
    int n;

    vector<ll> dist;
    vi depth;
    vector<vi> par;

    inline void dfs(int v, int p, int dep, ll dis, Tree& adj){
        depth[v] = dep, par[v][0] = p, dist[v] = dis;
        for(auto u : adj[v])
            if(u.first != p) dfs(u.first, v, dep + 1, dis + u.second, adj);
    }

public:

    void operator()(Tree& adj, int r){
        n = adj.size();
        par = vector<vi>(n, vi(__lg(n) + 1));
        depth.resize(n), dist.resize(n);
        dfs(r, r, 0, 0, adj);
        rep1(k, __lg(n))
            rep(i, n)
                par[i][k] = par[par[i][k - 1]][k - 1];
    }

    int lca(int u, int v){
        if(depth[u] < depth[v]) swap(u, v);

        for(int k = depth[u] - depth[v]; k; k -= 1 << __lg(k))
            u = par[u][__lg(k)];
        assert(depth[u] == depth[v]);
        if(u == v) return u;

        for(int k = __lg(n); k >= 0; k--)
            if(par[u][k] != par[v][k]) u = par[u][k], v = par[v][k];
        assert(par[u][0] == par[v][0]);
        return par[u][0];
    }

    inline ll distance(int u, int v){
        return dist[u] + dist[v] - 2 * dist[lca(u, v)];
    }

    inline int length(int u, int v){
        return depth[u] + depth[v] - 2 * depth[lca(u, v)];
    }
};

ll N, K;
Tree tree;
CentroidDecompostion decomp;
TreeDist dist;
vector<hash_table<int, hash_table<int, int, custom_hash>, custom_hash>> best;
vi so_far, upd;

//int main(){
int best_path(int _N, int _K, int H[][2], int L[]){

    #ifdef DEBUG
        //dbg::light = 1;
        freopen("debug", "w", stderr);
    #endif

    N = _N, K = _K; 
//  cin >> N >> K;
    tree.resize(N), best.resize(N), so_far.resize(K + 1);
    fill(all(so_far), N);
    debug(N, K);
    rep(i, N - 1){
        int u = H[i][0], v = H[i][1] , d = L[i];
        //int u, v, d; cin >> u >> v >> d;
        tree[u].pb({v, d}), tree[v].pb({u, d});
    }
        
    int tmp = decomp(tree);

    //debug(decomp.par);
    debug(string("centroid done"))
    dist(tree, tmp);
  //  debug(dist.depth, dist.dist);
    //Tree().swap(tree);
    rep(i, N){
        for(int t = decomp[i], p = i; t != -1; p = t, t = decomp[t]){
            auto& x = best[t][p]; 
            ll d = dist.distance(i, t);
            if(d > K) continue;
            auto it = x.find(d);
            if(it != x.end()) ckmin(it->second, dist.length(i, t));
            else x[d] = dist.length(i, t);
        }
    }   
    //vi().swap(decomp.par), vi().swap(dist.depth), vector<ll>().swap(dist.dist)
    vector<vi>().swap(dist.par);
    //debug(best);
    int ans = N;
    
    auto check = [&](int v){
        so_far[0] = 0;
        for(auto& mp : best[v]){
            for(auto& p : mp.second)
                    ckmin(ans, so_far[K - p.first] + p.second);                
            for(auto& p : mp.second){
                if(so_far[p.first] < N)
                    ckmin(so_far[p.first], p.second);
                else
                    so_far[p.first] = p.second, upd.pb(p.first);
            }
        }
        for(auto i : upd)
            so_far[i] = N;
        upd.clear();
        //debug(v, best[v]);
    };

    rep(i, N)
        check(i);
        

    if(ans >= N) ans = -1;
    
    //cout << ans << '\n';
    return ans;

    #ifdef DEBUG
        dbg::dout << "\nExecution time: " << clock() << "ms\n";
    #endif

    return 0;
}

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