oj.uz

Submission #922473

# Submission time Handle Problem Language Result Execution time Memory
922473 2024-02-05T14:37:39 Z AlphaMale06 Factories (JOI14_factories) C++14
15 / 100
 966 ms 211200 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][20];
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<20; 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=19; 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(n<5e4);
}

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 39472 KB Output is correct
2 Correct 415 ms 45792 KB Output is correct
3 Correct 872 ms 46064 KB Output is correct
4 Correct 836 ms 45908 KB Output is correct
5 Correct 420 ms 46112 KB Output is correct
6 Correct 149 ms 45908 KB Output is correct
7 Correct 857 ms 45888 KB Output is correct
8 Correct 888 ms 46060 KB Output is correct
9 Correct 413 ms 46112 KB Output is correct
10 Correct 148 ms 45792 KB Output is correct
11 Correct 858 ms 45796 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 39256 KB Output is correct
2 Runtime error 966 ms 211200 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 39472 KB Output is correct
2 Correct 415 ms 45792 KB Output is correct
3 Correct 872 ms 46064 KB Output is correct
4 Correct 836 ms 45908 KB Output is correct
5 Correct 420 ms 46112 KB Output is correct
6 Correct 149 ms 45908 KB Output is correct
7 Correct 857 ms 45888 KB Output is correct
8 Correct 888 ms 46060 KB Output is correct
9 Correct 413 ms 46112 KB Output is correct
10 Correct 148 ms 45792 KB Output is correct
11 Correct 858 ms 45796 KB Output is correct
12 Correct 8 ms 39256 KB Output is correct
13 Runtime error 966 ms 211200 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -