oj.uz

Submission #709528

# Submission time Handle Problem Language Result Execution time Memory
709528 2023-03-13T20:51:03 Z Ahmed57 Factories (JOI14_factories) C++14
100 / 100
 6718 ms 340116 KB 
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>

using namespace std;
vector<pair<int,long long>> adj[500001];
int hi[500001];
int P[500001][19];
long long sum[500001][19];
void dfs(int i,int pr,long long len){
    hi[i] = hi[pr]+1;
    P[i][0]= pr;
    sum[i][0] =len;
    for(int j = 1;j<19;j++){
        P[i][j] = P[P[i][j-1]][j-1];
        sum[i][j]= sum[i][j-1]+sum[P[i][j-1]][j-1];
    }
    for(auto j:adj[i]){
        if(j.first!=pr){
            dfs(j.first,i,j.second);
        }
    }
}long long lca(int x,int y){
    long long su = 0;
    if(hi[x]<hi[y]) swap(x,y);
    for(int k=18;k>=0;k--)
    {
        if(hi[x]-(1<<k) >= hi[y]){
            su+=sum[x][k];
            x=P[x][k];
        }
    }
    if(x==y) return su;
    for(int k=18;k>=0;k--)
    {
        if(P[x][k] != P[y][k]){
            su+=sum[x][k]+sum[y][k];
            x=P[x][k],y=P[y][k];
        }
    }
    return su+sum[x][0]+sum[y][0];
}
int sz[500001];
int vis[500001];
int par[500001];
long long best[500001];
int vi[500001];
int va = 1;
vector<long long> dist[500001];
void computedist(int n){
    for(int i = 0;i<n;i++){
        for(int j = i;j!=-1;j=par[j]){
            dist[i].push_back(lca(j,i));
        }
    }
}
void upd(int i){
    long long s = i;
    int idx = 0;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        best[s] = min(best[s],dist[i][idx]);
        s= par[s];
        idx++;
    }
}
long long ans(int i){
    long long s = i , re = 1e18;
    int idx = 0;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        re = min(re,best[s]+dist[i][idx]);
        s= par[s];
        idx++;
    }
    return re;
}
int find_size(int v, int p = -1) {
    if(vis[v]) return 0;
    sz[v] = 1;
    for(auto x: adj[v]) {
        if (x.first != p) {
            sz[v] += find_size(x.first, v);
        }
    }
    return sz[v];
}
int find_centroid(int v, int p, int n) {
    for (auto x: adj[v]) {
        if (x.first != p) {
            if (!vis[x.first] && sz[x.first] > n / 2) {
                return find_centroid(x.first, v, n);
            }
        }
    }
    return v;
}
void centroid(int v = 0, int p = -1) {
    find_size(v);
    int c = find_centroid(v,-1,sz[v]);
    vis[c] = true;
    par[c] = p;
    for(auto x:adj[c]) {
        if (!vis[x.first]) {
            centroid(x.first, c);
        }
    }
}
void Init(int N,int A[],int B[],int D[]){
    for(int i = 0;i<N-1;i++){
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    centroid();
    dfs(0,0,0);
    computedist(N);
}
long long Query(int S, int X[], int T,int Y[]) {
	for(int i = 0;i<S;i++){
        upd(X[i]);
	}
	long long Res = 1e18;
	for(int i = 0;i<T;i++){
        Res = min(Res,ans(Y[i]));
	}
	va++;
	return Res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24316 KB Output is correct
2 Correct 254 ms 33780 KB Output is correct
3 Correct 302 ms 34108 KB Output is correct
4 Correct 274 ms 34016 KB Output is correct
5 Correct 288 ms 34360 KB Output is correct
6 Correct 208 ms 33540 KB Output is correct
7 Correct 281 ms 34052 KB Output is correct
8 Correct 294 ms 33996 KB Output is correct
9 Correct 285 ms 34400 KB Output is correct
10 Correct 191 ms 33484 KB Output is correct
11 Correct 286 ms 34040 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24148 KB Output is correct
2 Correct 2055 ms 253752 KB Output is correct
3 Correct 4496 ms 289296 KB Output is correct
4 Correct 694 ms 200840 KB Output is correct
5 Correct 6072 ms 340116 KB Output is correct
6 Correct 4692 ms 291880 KB Output is correct
7 Correct 974 ms 93436 KB Output is correct
8 Correct 348 ms 82116 KB Output is correct
9 Correct 1200 ms 101488 KB Output is correct
10 Correct 959 ms 94548 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 24316 KB Output is correct
2 Correct 254 ms 33780 KB Output is correct
3 Correct 302 ms 34108 KB Output is correct
4 Correct 274 ms 34016 KB Output is correct
5 Correct 288 ms 34360 KB Output is correct
6 Correct 208 ms 33540 KB Output is correct
7 Correct 281 ms 34052 KB Output is correct
8 Correct 294 ms 33996 KB Output is correct
9 Correct 285 ms 34400 KB Output is correct
10 Correct 191 ms 33484 KB Output is correct
11 Correct 286 ms 34040 KB Output is correct
12 Correct 14 ms 24148 KB Output is correct
13 Correct 2055 ms 253752 KB Output is correct
14 Correct 4496 ms 289296 KB Output is correct
15 Correct 694 ms 200840 KB Output is correct
16 Correct 6072 ms 340116 KB Output is correct
17 Correct 4692 ms 291880 KB Output is correct
18 Correct 974 ms 93436 KB Output is correct
19 Correct 348 ms 82116 KB Output is correct
20 Correct 1200 ms 101488 KB Output is correct
21 Correct 959 ms 94548 KB Output is correct
22 Correct 2241 ms 255796 KB Output is correct
23 Correct 2305 ms 259296 KB Output is correct
24 Correct 5048 ms 292560 KB Output is correct
25 Correct 4933 ms 296372 KB Output is correct
26 Correct 4934 ms 293248 KB Output is correct
27 Correct 6718 ms 339824 KB Output is correct
28 Correct 843 ms 211248 KB Output is correct
29 Correct 5047 ms 297352 KB Output is correct
30 Correct 5161 ms 314668 KB Output is correct
31 Correct 5294 ms 315300 KB Output is correct
32 Correct 1175 ms 102308 KB Output is correct
33 Correct 382 ms 82456 KB Output is correct
34 Correct 632 ms 88396 KB Output is correct
35 Correct 633 ms 88676 KB Output is correct
36 Correct 932 ms 91512 KB Output is correct
37 Correct 996 ms 91548 KB Output is correct