oj.uz

Submission #660356

# Submission time Handle Problem Language Result Execution time Memory
660356 2022-11-21T17:39:13 Z rafatoa Factories (JOI14_factories) C++17
100 / 100
 5545 ms 205772 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 31-__builtin_clz(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 13 ms 12500 KB Output is correct
2 Correct 379 ms 21476 KB Output is correct
3 Correct 493 ms 21724 KB Output is correct
4 Correct 496 ms 21496 KB Output is correct
5 Correct 522 ms 21984 KB Output is correct
6 Correct 196 ms 21452 KB Output is correct
7 Correct 496 ms 21556 KB Output is correct
8 Correct 492 ms 21548 KB Output is correct
9 Correct 547 ms 21912 KB Output is correct
10 Correct 197 ms 21452 KB Output is correct
11 Correct 489 ms 21516 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 2117 ms 161420 KB Output is correct
3 Correct 2817 ms 165664 KB Output is correct
4 Correct 875 ms 162164 KB Output is correct
5 Correct 4035 ms 205772 KB Output is correct
6 Correct 3083 ms 166808 KB Output is correct
7 Correct 1499 ms 50952 KB Output is correct
8 Correct 455 ms 51084 KB Output is correct
9 Correct 1716 ms 56268 KB Output is correct
10 Correct 1644 ms 52168 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12500 KB Output is correct
2 Correct 379 ms 21476 KB Output is correct
3 Correct 493 ms 21724 KB Output is correct
4 Correct 496 ms 21496 KB Output is correct
5 Correct 522 ms 21984 KB Output is correct
6 Correct 196 ms 21452 KB Output is correct
7 Correct 496 ms 21556 KB Output is correct
8 Correct 492 ms 21548 KB Output is correct
9 Correct 547 ms 21912 KB Output is correct
10 Correct 197 ms 21452 KB Output is correct
11 Correct 489 ms 21516 KB Output is correct
12 Correct 7 ms 12244 KB Output is correct
13 Correct 2117 ms 161420 KB Output is correct
14 Correct 2817 ms 165664 KB Output is correct
15 Correct 875 ms 162164 KB Output is correct
16 Correct 4035 ms 205772 KB Output is correct
17 Correct 3083 ms 166808 KB Output is correct
18 Correct 1499 ms 50952 KB Output is correct
19 Correct 455 ms 51084 KB Output is correct
20 Correct 1716 ms 56268 KB Output is correct
21 Correct 1644 ms 52168 KB Output is correct
22 Correct 2814 ms 163088 KB Output is correct
23 Correct 2992 ms 165444 KB Output is correct
24 Correct 4090 ms 167032 KB Output is correct
25 Correct 3996 ms 170844 KB Output is correct
26 Correct 4126 ms 167424 KB Output is correct
27 Correct 5545 ms 199560 KB Output is correct
28 Correct 1091 ms 166024 KB Output is correct
29 Correct 4373 ms 166772 KB Output is correct
30 Correct 4317 ms 165912 KB Output is correct
31 Correct 4332 ms 166864 KB Output is correct
32 Correct 1830 ms 57580 KB Output is correct
33 Correct 492 ms 51516 KB Output is correct
34 Correct 1158 ms 48608 KB Output is correct
35 Correct 1159 ms 48708 KB Output is correct
36 Correct 1459 ms 49432 KB Output is correct
37 Correct 1527 ms 49404 KB Output is correct