oj.uz

Submission #660352

# Submission time Handle Problem Language Result Execution time Memory
660352 2022-11-21T17:30:57 Z rafatoa Factories (JOI14_factories) C++17
100 / 100
 5283 ms 205688 KB 
#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;

const int N = 5e5+1;

int n;
vpi adj[N];
int st[2*N][21];
long long d[N], dc[N], sub[N], par[N], best[N], vis[N], tin[N], eul[2*N];
bool del[N];

int tt = 0;

int lg2(int x){
    return 63-__builtin_clzll(x);
}

int cmp(int a, int b){
    return (d[a] < d[b] ? a : b);
}

int lca(int a, int b){
    if(tin[a] > tin[b]) swap(a, b);
    int len = tin[b]-tin[a]+1, lg = lg2(len);
    return cmp(st[tin[a]][lg], st[tin[b]-(1LL<<lg)+1][lg]);
}

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

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

    for(int i=0; i<2*n-1; i++) st[i][0] = eul[i];
    for(int j=1; j<=20; j++)
    for(int i=0; i+(1LL<<j)-1<2*n-1; i++)
        st[i][j] = cmp(st[i][j-1], st[i+(1LL<<(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;
    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];
        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];
        }
    }

    for(int i=0; i<S; i++){
        X[i]++;
        int curr = X[i];
        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];
        }
    }

    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12500 KB Output is correct
2 Correct 372 ms 21492 KB Output is correct
3 Correct 497 ms 21460 KB Output is correct
4 Correct 493 ms 21544 KB Output is correct
5 Correct 518 ms 21984 KB Output is correct
6 Correct 202 ms 21452 KB Output is correct
7 Correct 487 ms 21488 KB Output is correct
8 Correct 513 ms 21708 KB Output is correct
9 Correct 526 ms 21972 KB Output is correct
10 Correct 202 ms 21484 KB Output is correct
11 Correct 504 ms 21580 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12372 KB Output is correct
2 Correct 2087 ms 161368 KB Output is correct
3 Correct 2838 ms 165716 KB Output is correct
4 Correct 870 ms 162112 KB Output is correct
5 Correct 3889 ms 205688 KB Output is correct
6 Correct 2958 ms 166736 KB Output is correct
7 Correct 1509 ms 50856 KB Output is correct
8 Correct 450 ms 51104 KB Output is correct
9 Correct 1756 ms 56196 KB Output is correct
10 Correct 1526 ms 52000 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12500 KB Output is correct
2 Correct 372 ms 21492 KB Output is correct
3 Correct 497 ms 21460 KB Output is correct
4 Correct 493 ms 21544 KB Output is correct
5 Correct 518 ms 21984 KB Output is correct
6 Correct 202 ms 21452 KB Output is correct
7 Correct 487 ms 21488 KB Output is correct
8 Correct 513 ms 21708 KB Output is correct
9 Correct 526 ms 21972 KB Output is correct
10 Correct 202 ms 21484 KB Output is correct
11 Correct 504 ms 21580 KB Output is correct
12 Correct 7 ms 12372 KB Output is correct
13 Correct 2087 ms 161368 KB Output is correct
14 Correct 2838 ms 165716 KB Output is correct
15 Correct 870 ms 162112 KB Output is correct
16 Correct 3889 ms 205688 KB Output is correct
17 Correct 2958 ms 166736 KB Output is correct
18 Correct 1509 ms 50856 KB Output is correct
19 Correct 450 ms 51104 KB Output is correct
20 Correct 1756 ms 56196 KB Output is correct
21 Correct 1526 ms 52000 KB Output is correct
22 Correct 2907 ms 162888 KB Output is correct
23 Correct 2883 ms 165320 KB Output is correct
24 Correct 4086 ms 167132 KB Output is correct
25 Correct 4132 ms 170736 KB Output is correct
26 Correct 4127 ms 167404 KB Output is correct
27 Correct 5283 ms 199600 KB Output is correct
28 Correct 1065 ms 166256 KB Output is correct
29 Correct 4113 ms 166832 KB Output is correct
30 Correct 4130 ms 165932 KB Output is correct
31 Correct 4040 ms 167096 KB Output is correct
32 Correct 1615 ms 57584 KB Output is correct
33 Correct 450 ms 51456 KB Output is correct
34 Correct 1076 ms 48532 KB Output is correct
35 Correct 1113 ms 48420 KB Output is correct
36 Correct 1442 ms 49544 KB Output is correct
37 Correct 1489 ms 49316 KB Output is correct