oj.uz

답안 #922467

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922467 2024-02-05T14:28:09 Z AlphaMale06 공장들 (JOI14_factories) C++17
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][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);
}

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 num=0;
        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]));
            num++;
            assert(num<30);
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39516 KB Output is correct
2 Correct 427 ms 54608 KB Output is correct
3 Correct 916 ms 54612 KB Output is correct
4 Correct 856 ms 54612 KB Output is correct
5 Correct 432 ms 54816 KB Output is correct
6 Correct 200 ms 54596 KB Output is correct
7 Correct 879 ms 54592 KB Output is correct
8 Correct 907 ms 54600 KB Output is correct
9 Correct 431 ms 54748 KB Output is correct
10 Correct 159 ms 54616 KB Output is correct
11 Correct 867 ms 54492 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 39260 KB Output is correct
2 Execution timed out 8047 ms 125124 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 18 ms 39516 KB Output is correct
2 Correct 427 ms 54608 KB Output is correct
3 Correct 916 ms 54612 KB Output is correct
4 Correct 856 ms 54612 KB Output is correct
5 Correct 432 ms 54816 KB Output is correct
6 Correct 200 ms 54596 KB Output is correct
7 Correct 879 ms 54592 KB Output is correct
8 Correct 907 ms 54600 KB Output is correct
9 Correct 431 ms 54748 KB Output is correct
10 Correct 159 ms 54616 KB Output is correct
11 Correct 867 ms 54492 KB Output is correct
12 Correct 9 ms 39260 KB Output is correct
13 Execution timed out 8047 ms 125124 KB Time limit exceeded
14 Halted 0 ms 0 KB -