Submission #587844

#	Time	Username	Problem	Language	Result	Execution time	Memory
587844		MohamedFaresNebili	Factories (JOI14_factories)	C++14	100 / 100	3828 ms	197184 KiB

factories

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

        using namespace std;

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

        #define ff first
        #define ss second
        #define pb push_back
        #define all(x) (x).begin(), (x).end()
        #define lb lower_bound

        const int MOD = 1000 * 1000 * 1000 + 7;

        vector<pair<int, ll>> adj[500001];
        int par[500001], level[500001], sz[500001];
        ll dist[500001][22], ans[500001];
        bool rem[500001];

        /// CENTROID DECOMPOSITION :

        int dfs_size(int v, int p) {
            sz[v] = 1;
            for(auto u: adj[v]) {
                if(u.ff == p || rem[u.ff]) continue;
                sz[v] += dfs_size(u.ff, v);
            }
            return sz[v];
        }
        int centroid(int v, int p, int  N) {
            for(auto u : adj[v]) {
                if(u.ff == p || rem[u.ff]) continue;
                if(sz[u.ff] >= N / 2)
                    return centroid(u.ff, v, N);
            }
            return v;
        }
        void dfs(int v, int p, int L) {
            for(auto u : adj[v]) {
                if(u.ff == p || rem[u.ff]) continue;
                dist[u.ff][L] = dist[v][L] + u.ss;
                dfs(u.ff, v, L);
            }
        }
        void build(int v, int p) {
            int N = dfs_size(v, p);
            int C = centroid(v, p, N);
            level[C] = (p != -1 ? level[p] + 1 : 0);
            par[C] = p; dfs(C, C, level[C]); rem[C] = 1;
            for(auto u : adj[C]) {
                if(rem[u.ff]) continue;
                build(u.ff, C);
            }
        }

        void Init(int N, int A[], int B[], int D[]) {
            for(int l = 0; l < N - 1; l++) {
                int U = A[l], V = B[l], W = D[l];
                adj[U].pb({V, W}), adj[V].pb({U, W});
            }
            for(int l = 0; l < N; l++) ans[l] = 1e18 + 7;
            build(0, -1);
        }
        void update(int U) {
            int V = U;
            for(; V != -1; V = par[V])
                ans[V] = min(ans[V], dist[U][level[V]]);
        }
        ll query(int U) {
            int V = U; ll res = 1e18 + 7;
            for(; V != -1; V = par[V])
                res = min(res, ans[V] + dist[U][level[V]]);
            return res;
        }
        void reset(int U) {
            for(; U != -1; U = par[U])
                ans[U] = 1e18 + 7;
        }
        long long Query(int S, int X[], int T, int Y[]) {
            ll res = 1e18 + 7;
            for(int l = 0; l < S; l++) update(X[l]);
            for(int l = 0; l < T; l++)
                res = min(res, query(Y[l]));
            for(int l = 0; l < S; l++) reset(X[l]);
            return res;
        }

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67