oj.uz

Submission #660359

# Submission time Handle Problem Language Result Execution time Memory
660359 2022-11-21T17:45:22 Z rafatoa Factories (JOI14_factories) C++17
100 / 100
 7252 ms 275796 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 adjc[N];
set<int> 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];
 
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]:adjc[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:adj[s]){
            if(u == e) continue;
            dfs_sub(u, s);
            sub[s] += sub[u];
        }
    };
 
    function<int(int, int, int)> centroid = [&](int s, int e, int sz){
        for(auto u:adj[s])
            if(u != e && 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;
 
        for(auto u:adj[C]){
            adj[u].erase(C);
            decompose(u, C);
        }
        adj[C].clear();
    };
    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++){
        adjc[A[i]+1].pb({B[i]+1, D[i]});
        adjc[B[i]+1].pb({A[i]+1, D[i]});
        adj[A[i]+1].insert(B[i]+1);
        adj[B[i]+1].insert(A[i]+1);
    }
 
    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 30 ms 36040 KB Output is correct
2 Correct 427 ms 45480 KB Output is correct
3 Correct 529 ms 45500 KB Output is correct
4 Correct 552 ms 45508 KB Output is correct
5 Correct 529 ms 45940 KB Output is correct
6 Correct 225 ms 45496 KB Output is correct
7 Correct 503 ms 45540 KB Output is correct
8 Correct 526 ms 45480 KB Output is correct
9 Correct 550 ms 45864 KB Output is correct
10 Correct 218 ms 45456 KB Output is correct
11 Correct 529 ms 45496 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 35888 KB Output is correct
2 Correct 2601 ms 231416 KB Output is correct
3 Correct 3453 ms 235656 KB Output is correct
4 Correct 1634 ms 232148 KB Output is correct
5 Correct 4662 ms 275796 KB Output is correct
6 Correct 3541 ms 236692 KB Output is correct
7 Correct 1739 ms 83764 KB Output is correct
8 Correct 587 ms 83924 KB Output is correct
9 Correct 1886 ms 89108 KB Output is correct
10 Correct 1825 ms 84764 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 36040 KB Output is correct
2 Correct 427 ms 45480 KB Output is correct
3 Correct 529 ms 45500 KB Output is correct
4 Correct 552 ms 45508 KB Output is correct
5 Correct 529 ms 45940 KB Output is correct
6 Correct 225 ms 45496 KB Output is correct
7 Correct 503 ms 45540 KB Output is correct
8 Correct 526 ms 45480 KB Output is correct
9 Correct 550 ms 45864 KB Output is correct
10 Correct 218 ms 45456 KB Output is correct
11 Correct 529 ms 45496 KB Output is correct
12 Correct 19 ms 35888 KB Output is correct
13 Correct 2601 ms 231416 KB Output is correct
14 Correct 3453 ms 235656 KB Output is correct
15 Correct 1634 ms 232148 KB Output is correct
16 Correct 4662 ms 275796 KB Output is correct
17 Correct 3541 ms 236692 KB Output is correct
18 Correct 1739 ms 83764 KB Output is correct
19 Correct 587 ms 83924 KB Output is correct
20 Correct 1886 ms 89108 KB Output is correct
21 Correct 1825 ms 84764 KB Output is correct
22 Correct 3580 ms 232860 KB Output is correct
23 Correct 3838 ms 235272 KB Output is correct
24 Correct 5000 ms 236908 KB Output is correct
25 Correct 5083 ms 240716 KB Output is correct
26 Correct 5591 ms 237440 KB Output is correct
27 Correct 7252 ms 269652 KB Output is correct
28 Correct 1998 ms 236260 KB Output is correct
29 Correct 5032 ms 236828 KB Output is correct
30 Correct 4834 ms 235856 KB Output is correct
31 Correct 4982 ms 237020 KB Output is correct
32 Correct 2275 ms 90564 KB Output is correct
33 Correct 634 ms 84504 KB Output is correct
34 Correct 1334 ms 81484 KB Output is correct
35 Correct 1653 ms 81748 KB Output is correct
36 Correct 1786 ms 82568 KB Output is correct
37 Correct 1744 ms 82580 KB Output is correct