oj.uz

Submission #709521

# Submission time Handle Problem Language Result Execution time Memory
709521 2023-03-13T20:34:41 Z Ahmed57 Factories (JOI14_factories) C++14
15 / 100
 1792 ms 33540 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[200001];
int hi[200001];
int P[200001][18];
long long sum[200001][18];
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<18;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=17;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=17;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[200001];
int vis[200001];
int par[200001];
long long best[200001];
int vi[200001];
int va = 1;
void upd(int i){
    long long s = i;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        best[s] = min(best[s],lca(i,s));
        s= par[s];
    }
}
long long ans(int i){
    long long s = i , re = 1e18;
    while(s!=-1){
        if(vi[s]!=va){
            vi[s] =va;
            best[s] = 1e18;
        }
        re = min(re,best[s]+lca(i,s));
        s= par[s];
    }
    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);
}
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 16 ms 5588 KB Output is correct
2 Correct 585 ms 23932 KB Output is correct
3 Correct 1372 ms 24308 KB Output is correct
4 Correct 1293 ms 24000 KB Output is correct
5 Correct 1792 ms 24332 KB Output is correct
6 Correct 244 ms 24012 KB Output is correct
7 Correct 1309 ms 24012 KB Output is correct
8 Correct 1479 ms 23984 KB Output is correct
9 Correct 1695 ms 24360 KB Output is correct
10 Correct 265 ms 24008 KB Output is correct
11 Correct 1348 ms 24004 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5332 KB Output is correct
2 Runtime error 309 ms 33540 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5588 KB Output is correct
2 Correct 585 ms 23932 KB Output is correct
3 Correct 1372 ms 24308 KB Output is correct
4 Correct 1293 ms 24000 KB Output is correct
5 Correct 1792 ms 24332 KB Output is correct
6 Correct 244 ms 24012 KB Output is correct
7 Correct 1309 ms 24012 KB Output is correct
8 Correct 1479 ms 23984 KB Output is correct
9 Correct 1695 ms 24360 KB Output is correct
10 Correct 265 ms 24008 KB Output is correct
11 Correct 1348 ms 24004 KB Output is correct
12 Correct 5 ms 5332 KB Output is correct
13 Runtime error 309 ms 33540 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -