oj.uz

Submission #922456

# Submission time Handle Problem Language Result Execution time Memory
922456 2024-02-05T14:15:11 Z AlphaMale06 Factories (JOI14_factories) C++14
0 / 100
 38 ms 75564 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);
    assert(0);
}

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 num=0;
        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;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:103:13: warning: unused variable 'num' [-Wunused-variable]
  103 |         int num=0;
      |             ^~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 75344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 35 ms 75564 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 75344 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -