oj.uz

Submission #709524

# Submission time Handle Problem Language Result Execution time Memory
709524 2023-03-13T20:39:14 Z Ahmed57 Factories (JOI14_factories) C++17
15 / 100
 8000 ms 201800 KB 
#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;
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 23 ms 12500 KB Output is correct
2 Correct 901 ms 21880 KB Output is correct
3 Correct 1618 ms 21880 KB Output is correct
4 Correct 1537 ms 21764 KB Output is correct
5 Correct 1987 ms 21928 KB Output is correct
6 Correct 279 ms 21624 KB Output is correct
7 Correct 1578 ms 21640 KB Output is correct
8 Correct 1683 ms 21780 KB Output is correct
9 Correct 1958 ms 22052 KB Output is correct
10 Correct 269 ms 21676 KB Output is correct
11 Correct 1592 ms 21772 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12360 KB Output is correct
2 Correct 2807 ms 175744 KB Output is correct
3 Correct 7305 ms 178716 KB Output is correct
4 Correct 877 ms 173600 KB Output is correct
5 Execution timed out 8074 ms 201800 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 12500 KB Output is correct
2 Correct 901 ms 21880 KB Output is correct
3 Correct 1618 ms 21880 KB Output is correct
4 Correct 1537 ms 21764 KB Output is correct
5 Correct 1987 ms 21928 KB Output is correct
6 Correct 279 ms 21624 KB Output is correct
7 Correct 1578 ms 21640 KB Output is correct
8 Correct 1683 ms 21780 KB Output is correct
9 Correct 1958 ms 22052 KB Output is correct
10 Correct 269 ms 21676 KB Output is correct
11 Correct 1592 ms 21772 KB Output is correct
12 Correct 9 ms 12360 KB Output is correct
13 Correct 2807 ms 175744 KB Output is correct
14 Correct 7305 ms 178716 KB Output is correct
15 Correct 877 ms 173600 KB Output is correct
16 Execution timed out 8074 ms 201800 KB Time limit exceeded
17 Halted 0 ms 0 KB -