Submission #660185

#	Time	Username	Problem	Language	Result	Execution time	Memory
660185		rafatoa	Factories (JOI14_factories)	C++17	15 / 100	8090 ms	128692 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")

#define F first
// #define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define double ld
// #define int long long
const long long INF = 4e18;

int n;
vector<vpi> adj;
vector<long long> d, dc, sub, par, best, vis;
vvi up;
vb del;

int tt = 0;

int lca(int a, int b){
    if(d[a] > d[b]) swap(a, b);
    for(int j=0; j<=20; j++)
        if((1LL<<j)&(d[b]-d[a])) b = up[b][j];
    if(a == b) return a;
    for(int j=20; j>=0; j--)
        if(up[a][j] != up[b][j])
            a = up[a][j], b = up[b][j];
    return up[a][0];  
}

long long dist(int a, int b){
    return dc[a]+dc[b]-2*dc[lca(a, b)];
}

void build(){
    d = dc = sub = par = vis = best = vector<long long>(n+1);
    up = vvi(n+1, vi(21));
    del = vb(n+1);

    function<void(int, int)> dfs0 = [&](int s, int e){
        for(auto [u, c]:adj[s]){
            if(u == e) continue;
            d[u] = d[s]+1;
            dc[u] = dc[s]+c;
            up[u][0] = s;
            dfs0(u, s);
        }
    };
    dfs0(1, 0);

    for(int j=1; j<=20; j++)
    for(int i=1; i<=n; i++)
        up[i][j] = up[up[i][j-1]][j-1];

    //START_CENTROID

    function<void(int, int)> dfs_sub = [&](int s, int e){
        sub[s] = 1;
        for(auto [u, c]:adj[s]){
            if(u == e || del[u]) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };

    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto [u, c]:adj[s])
            if(u != e && !del[u] && sub[u] > sz/2) return centroid(u, s, sz);
        return s;
    };

    function<void(int, int)> decompose = [&](int s, int p){
        dfs_sub(s, 0);
        int C = centroid(s, 0, sub[s]);
        par[C] = p;

        del[C] = 1;
        for(auto [u, c]:adj[C])
            if(!del[u]) decompose(u, C);
    };
    decompose(1, -1);

    //END_CENTROID
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    adj = vector<vpi>(n+1);
    for(int i=0; i<n-1; i++){
        adj[A[i]+1].pb({B[i]+1, D[i]});
        adj[B[i]+1].pb({A[i]+1, D[i]});
    }

    build();
}

long long Query(int S, int X[], int T, int Y[]){
    tt++;
    long long ans = INF;
    
    for(int i=0; i<T; i++){
        Y[i]++;
        int curr = Y[i];
        int x = 0;
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            best[curr] = min(best[curr], dist(curr, Y[i]));
            curr = par[curr];
            ++x;
        }
        if(x > 25) assert(0);
    }

    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i];
        int x = 0;
        while(curr != -1){
            if(vis[curr] < tt){
                vis[curr] = tt;
                best[curr] = INF;
            }
            ans = min(ans, best[curr]+dist(curr, X[i]));
            curr = par[curr];
            ++x;
        }
        if(x > 25) assert(0);
    }

    return ans;
}

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