Submission #975097

#	Time	Username	Problem	Language	Result	Execution time	Memory
975097		Amaarsaa	Race (IOI11_race)	C++11	100 / 100	505 ms	41280 KiB

race

#include <iostream>
#include <algorithm>
#include <vector>
#include <chrono>
#include <cmath>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

typedef int_fast8_t  int8;
typedef int_fast16_t int16;
typedef int_fast32_t int32;
typedef int_fast64_t int64;
typedef int_fast64_t ll;

typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll>   pll;
typedef pair<ll, pll>  plll;

#define PB push_back
#define PF push_front
#define MP make_pair
#define FF first
#define SS second

namespace hash0 {
    const double PI = acos(-1);

    struct chash { 
        const uint64_t C = ll(2e18*PI)+71; 
        const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); 

        inline ll operator()(ll x) const { return __builtin_bswap64((x ^ RANDOM) * C); }

        inline ll operator()(pii p) const { return __builtin_bswap64((p.FF ^ RANDOM) * C) + p.SS; }
    };

    template<class K, class V> 
    using fast_map = gp_hash_table<K, V, chash>;

    template<class K> 
    using fast_set = fast_map<K, null_type>;
}

using namespace hash0;

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
    return os << '(' << p.FF << ", " << p.SS << ')';
}

template<typename T1, typename T2>
ostream& operator<<(ostream& os, const fast_map<T1, T2>& s) {
    os << '[';
    if (s.size()) {
        os << *s.begin();
        for (auto i = ++s.begin(); i != s.end(); i++)
            os << ", " << (*i);
    }
    return os << ']';
}

int N, K;
vector<pii> adj[200005];

int W[200005];
bool R[200005];

int dfs_w(int u, int p) {
    W[u] = 1;
    for (pii v : adj[u])
        if (v.FF != p && !R[v.FF])
            W[u] += dfs_w(v.FF, u);
    return W[u];
}

int centroid(int u, int n, int p) {
    for (pii v : adj[u])
        if (v.FF != p && !R[v.FF])
            if (W[v.FF] * 2 > n)
                return centroid(v.FF, n, u);
    return u;
}

int ans = 2000000011;
vector<pii> V;

void dfs_u(int u, int p, int d, int t) {
    if (d > K || t > ans)
        return;
    
    V.PB(MP(d, t));

    for (pii v : adj[u])
        if (v.FF != p && !R[v.FF])
            dfs_u(v.FF, u, d + v.SS, t + 1);
}

void init_cd(int u) {
    u = centroid(u, dfs_w(u, -1), -1);

    fast_map<int, int> M;
    for (pii v : adj[u]) {
        if (R[v.FF])
            continue;
        dfs_u(v.FF, u, v.SS, 1);
        for (pii x : V) {
	        if (M.find(K - x.FF) != M.end()) 
		        ans = min(ans, M[K - x.FF] + x.SS);
	        else if (x.FF == K) 
		        ans = min(ans, x.SS);
	    }
	    for (pii x : V) {
	        if (M.find(x.FF) == M.end()) 
		        M[x.FF] = x.SS;
	        else 
		        M[x.FF] = min(M[x.FF], x.SS);
	    }
	    V.clear();
    }

    R[u] = 1;
    for (pii v : adj[u])
        if (!R[v.FF])
            init_cd(v.FF);
}

int best_path(int n, int k, int h[][2], int l[]) {
    N = n, K = k;
    for (int i = 0; i < n - 1; i++) {
        adj[h[i][0]].PB(MP(h[i][1], l[i]));
        adj[h[i][1]].PB(MP(h[i][0], l[i]));
    }
    init_cd(0);
    return ans == 2000000011 ? -1 : ans;
}

Compilation message (stderr)

race.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      |

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