Submission #541345

#	Time	Username	Problem	Language	Result	Execution time	Memory
541345		MohamedFaresNebili	Race (IOI11_race)	C++14	100 / 100	908 ms	37104 KiB

race

#include <bits/stdc++.h>
#include "race.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")

        using namespace std;

        using ll = long long;
        using ii = pair<ll, ll>;

        #define ff first
        #define ss second
        #define pb push_back

        const int oo = 1e9 + 7;

        int n, k;
        vector<ii> adj[200001];
        int sub[200001];

        int res = oo;
        int calc[1000001], mx;
        bool rem[200001];

        /// CENTROID DECOMPOSITION :

        int dfs_size(int v, int p) {
            sub[v] = 1;
            for(auto u : adj[v]) {
                if(u.ff == p || rem[u.ff]) continue;
                sub[v] += dfs_size(u.ff, v);
            }
            return sub[v];
        }
        int centroid(int v, int p, int _n) {
            for(auto u : adj[v]) {
                if(u.ff == p || rem[u.ff]) continue;
                if(sub[u.ff] >= _n)
                    return centroid(u.ff, v, _n);
            }
            return v;
        }
        void dfs(int v, int p, bool state, int curr, int len) {
            if(len > k) return;

            mx = max(mx, len);

            if(state) calc[len] = min(calc[len], curr);
            else res = min(res, curr + calc[k - len]);

            for(auto u : adj[v]) {
                if(u.ff == p || rem[u.ff]) continue;
                dfs(u.ff, v, state, curr + 1, len + u.ss);
            }
        }
        void build(int v = 0) {
            int _n = dfs_size(v, -1) >> 1;
            int c = centroid(v, -1, _n);
            rem[c] = 1; mx = 0;
            for(auto u : adj[c]) {
                if(rem[u.ff]) continue;
                dfs(u.ff, c, 0, 1, u.ss);
                dfs(u.ff, c, 1, 1, u.ss);
            }
            fill(calc + 1, calc + mx + 1, oo);
            for(auto u : adj[c]) {
                if(rem[u.ff]) continue;
                build(u.ff);
            }
        }

        int best_path(int N, int K, int H[][2], int L[]) {
            n = N, k = K;
            for(int l = 0; l < n - 1; l++) {
                int u = H[l][0], v = H[l][1], w = L[l];
                adj[u].pb({v, w}); adj[v].pb({u, w});
            }
            fill(calc + 1, calc + 1000001, oo);
            build();
            return (res != oo ? res : -1);
        }

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