oj.uz

Submission #922452

# Submission time Handle Problem Language Result Execution time Memory
922452 2024-02-05T14:11:17 Z AlphaMale06 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 125124 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pb push_back
#define F first
#define S second


const int mxn = 5e5+3;

vector<pair<int, int>> adj[mxn];
int tin[mxn], tout[mxn];
int p[mxn][19];
ll dst[mxn];
int timer = -1;
int sz[mxn];
bool mark[mxn];
int cp[mxn];
ll cendist[mxn];
int en;

void dfs(int v, int par){
    p[v][0]=par;
    tin[v]=++timer;
    dst[v]+=dst[par];
    for(int i=1; i<19; i++){
        p[v][i]=p[p[v][i-1]][i-1];
    }
    for(auto to : adj[v]){
        if(to.F!=par){
            dst[to.F]=to.S;
            dfs(to.F, v);
        }
    }
    tout[v]=timer;
}


bool anc(int u, int v){
    if(tin[u]<=tin[v] && tout[u]>=tout[v])return 1;
    return 0;
}

int lca(int u, int v){
    if(anc(u, v))return u;
    if(anc(v, u))return v;
    for(int i=18; i>=0; i--){
        if(!anc(p[u][i], v))u=p[u][i];
    }
    return p[u][0];
}


ll dist(int u, int v){
    return dst[u]+dst[v]-2*dst[lca(u, v)];
}

int subtreesize(int v, int par){
    sz[v]=1;
    for(auto to : adj[v]){
        if(to.F==par || mark[to.F])continue;
        sz[v]+=subtreesize(to.F, v);
    }
    return sz[v];
}

int centr(int v, int par, int siz){
    for(auto to : adj[v]){
        if(to.F==par || mark[to.F])continue;
        if(sz[to.F]*2>siz)return centr(to.F, v, siz);
    }
    return v;
}

void decompose(int v, int par){
    int centroid = centr(v, par, subtreesize(v, par));
    mark[centroid]=1;
    if(par!=-1){
        cp[centroid]=par;
    }
    for(auto to : adj[centroid]){
        if(!mark[to.F])decompose(to.F, centroid);
    }
}


void Init(int n, int u[], int v[], int w[]) {
    en=n;
    for(int i=0; i<n-1; i++){
        adj[u[i]].pb({v[i], w[i]});
        adj[v[i]].pb({u[i], w[i]});
    }
    dfs(0, 0);
    for(int i=0; i< n; i++)cp[i]=i;
    decompose(0, -1);
}

long long Query(int sz1, int a[], int sz2, int b[]) {
    for(int i=0; i<en; i++)cendist[i]=1e14;
    for(int i=0; i<sz2; i++){
        int v=b[i];
        cendist[v]=0;
        while(v!=cp[v]){
            v=cp[v];
            cendist[v]=min(cendist[v], dist(b[i], v));
        }
    }
    ll ans=1e18;
    for(int i=0; i<sz1; i++){
        int v=a[i];
        ans=min(ans, cendist[v]+dist(v, a[i]));
        while(v!=cp[v]){
            v=cp[v];
            ans=min(ans, cendist[v]+dist(v, a[i]));
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39516 KB Output is correct
2 Correct 428 ms 55320 KB Output is correct
3 Correct 888 ms 55352 KB Output is correct
4 Correct 848 ms 55332 KB Output is correct
5 Correct 467 ms 55388 KB Output is correct
6 Correct 156 ms 55340 KB Output is correct
7 Correct 873 ms 55356 KB Output is correct
8 Correct 900 ms 55364 KB Output is correct
9 Correct 442 ms 55564 KB Output is correct
10 Correct 157 ms 55248 KB Output is correct
11 Correct 875 ms 55356 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39516 KB Output is correct
2 Execution timed out 8079 ms 125124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39516 KB Output is correct
2 Correct 428 ms 55320 KB Output is correct
3 Correct 888 ms 55352 KB Output is correct
4 Correct 848 ms 55332 KB Output is correct
5 Correct 467 ms 55388 KB Output is correct
6 Correct 156 ms 55340 KB Output is correct
7 Correct 873 ms 55356 KB Output is correct
8 Correct 900 ms 55364 KB Output is correct
9 Correct 442 ms 55564 KB Output is correct
10 Correct 157 ms 55248 KB Output is correct
11 Correct 875 ms 55356 KB Output is correct
12 Correct 10 ms 39516 KB Output is correct
13 Execution timed out 8079 ms 125124 KB Time limit exceeded
14 Halted 0 ms 0 KB -