oj.uz

Submission #922455

# Submission time Handle Problem Language Result Execution time Memory
922455 2024-02-05T14:13:52 Z AlphaMale06 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 106320 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 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));
            num++;
            assert(num<30);
        }
    }
    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 39256 KB Output is correct
2 Correct 432 ms 45868 KB Output is correct
3 Correct 912 ms 45888 KB Output is correct
4 Correct 939 ms 45884 KB Output is correct
5 Correct 425 ms 46164 KB Output is correct
6 Correct 175 ms 45904 KB Output is correct
7 Correct 909 ms 45892 KB Output is correct
8 Correct 924 ms 45900 KB Output is correct
9 Correct 446 ms 46124 KB Output is correct
10 Correct 158 ms 45792 KB Output is correct
11 Correct 910 ms 45892 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39256 KB Output is correct
2 Execution timed out 8013 ms 106320 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 39256 KB Output is correct
2 Correct 432 ms 45868 KB Output is correct
3 Correct 912 ms 45888 KB Output is correct
4 Correct 939 ms 45884 KB Output is correct
5 Correct 425 ms 46164 KB Output is correct
6 Correct 175 ms 45904 KB Output is correct
7 Correct 909 ms 45892 KB Output is correct
8 Correct 924 ms 45900 KB Output is correct
9 Correct 446 ms 46124 KB Output is correct
10 Correct 158 ms 45792 KB Output is correct
11 Correct 910 ms 45892 KB Output is correct
12 Correct 10 ms 39256 KB Output is correct
13 Execution timed out 8013 ms 106320 KB Time limit exceeded
14 Halted 0 ms 0 KB -