oj.uz

Submission #638133

# Submission time Handle Problem Language Result Execution time Memory
638133 2022-09-04T17:39:51 Z PoonYaPat Factories (JOI14_factories) C++14
100 / 100
 6190 ms 222252 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

vector<pii> adj[500001];
int par[500001],level[500001],p[500001][20],sz[500001];
ll dis[500001][20],d[500001],fact[500001];
bool mark[500001];

void dfs(int x, int parent) {
    p[x][0]=parent;
    level[x]=level[parent]+1;
    for (int i=1; i<20; ++i) {
        p[x][i]=p[p[x][i-1]][i-1];
    }

    for (auto s : adj[x]) {
        if (s.first==parent) continue;
        d[s.first]=d[x]+s.second;
        dfs(s.first,x);
    }
}

int lca(int x, int y) {
    if (level[x]<level[y]) swap(x,y);
    int dif=level[x]-level[y];
    for (int i=0; i<20; ++i) {
        if (dif&(1<<i)) x=p[x][i];
    }

    if (x==y) return x;

    for (int i=19; i>=0; --i) {
        if (p[x][i]!=p[y][i]) {
            x=p[x][i];
            y=p[y][i];
        }
    }
    return p[x][0];
}

ll dist(int x, int y) {
    return d[x]+d[y]-2*d[lca(x,y)];
}

int dfs_sz(int x, int parent) {
    int cnt=1;
    for (auto s : adj[x]) {
        if (s.first==parent || mark[s.first]) continue;
        cnt+=dfs_sz(s.first,x);
    }
    sz[x]=cnt;
    return cnt;
}

int find_cen(int x, int parent, int cnt) {
    for (auto s : adj[x]) {
        if (!mark[s.first] && s.first!=parent && sz[s.first]>cnt/2) return find_cen(s.first,x,cnt);
    }
    return x;
}

int decompose(int x, int parent) {
    int centroid=find_cen(x,x,dfs_sz(x,x));
    mark[centroid]=true;
    par[centroid]=parent;

    for (auto s : adj[centroid]) {
        if (!mark[s.first]) decompose(s.first,centroid);
    }

    return centroid;
}

void make_dis(int n) {
    for (int i=0; i<n; ++i) {
        int idx=0,m=i;
        while (m!=-1) {
            dis[i][idx++]=dist(i,m);
            m=par[m];
        }
    }
}

void add(int x) {
    int m=x,idx=0;
    while (m!=-1) {
        fact[m]=min(fact[m],dis[x][idx++]);
        m=par[m];
    }
}

ll find(int x) {
    int idx=0,m=x;
    ll mmin=1e15;
    while (m!=-1) {
        mmin=min(mmin,fact[m]+dis[x][idx++]);
        m=par[m];
    }
    return mmin;
}

void clear(int x) {
    while (x!=-1) {
        fact[x]=1e15;
        x=par[x];
    }
}

void Init(int n, int A[], int B[], int D[]) {
    for (int i=0; i<n-1; ++i) {
        adj[A[i]].push_back(pii(B[i],D[i]));
        adj[B[i]].push_back(pii(A[i],D[i]));
    }
    for (int i=0; i<n; ++i) fact[i]=1e15;
    dfs(0,-1); //root is 0
    decompose(0,-1);
    make_dis(n);
}

ll Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; ++i) add(X[i]);
    ll ans=1e15;
    for (int i=0; i<T; ++i) ans=min(ans,find(Y[i]));
    for (int i=0; i<S; ++i) clear(X[i]);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12628 KB Output is correct
2 Correct 289 ms 31168 KB Output is correct
3 Correct 316 ms 31096 KB Output is correct
4 Correct 323 ms 31112 KB Output is correct
5 Correct 318 ms 31292 KB Output is correct
6 Correct 204 ms 31112 KB Output is correct
7 Correct 292 ms 31140 KB Output is correct
8 Correct 284 ms 31052 KB Output is correct
9 Correct 293 ms 31320 KB Output is correct
10 Correct 201 ms 31072 KB Output is correct
11 Correct 276 ms 31032 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12316 KB Output is correct
2 Correct 2069 ms 193860 KB Output is correct
3 Correct 3942 ms 194572 KB Output is correct
4 Correct 708 ms 194192 KB Output is correct
5 Correct 5436 ms 217856 KB Output is correct
6 Correct 4099 ms 196740 KB Output is correct
7 Correct 864 ms 66876 KB Output is correct
8 Correct 337 ms 67716 KB Output is correct
9 Correct 1000 ms 70544 KB Output is correct
10 Correct 861 ms 68488 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12628 KB Output is correct
2 Correct 289 ms 31168 KB Output is correct
3 Correct 316 ms 31096 KB Output is correct
4 Correct 323 ms 31112 KB Output is correct
5 Correct 318 ms 31292 KB Output is correct
6 Correct 204 ms 31112 KB Output is correct
7 Correct 292 ms 31140 KB Output is correct
8 Correct 284 ms 31052 KB Output is correct
9 Correct 293 ms 31320 KB Output is correct
10 Correct 201 ms 31072 KB Output is correct
11 Correct 276 ms 31032 KB Output is correct
12 Correct 8 ms 12316 KB Output is correct
13 Correct 2069 ms 193860 KB Output is correct
14 Correct 3942 ms 194572 KB Output is correct
15 Correct 708 ms 194192 KB Output is correct
16 Correct 5436 ms 217856 KB Output is correct
17 Correct 4099 ms 196740 KB Output is correct
18 Correct 864 ms 66876 KB Output is correct
19 Correct 337 ms 67716 KB Output is correct
20 Correct 1000 ms 70544 KB Output is correct
21 Correct 861 ms 68488 KB Output is correct
22 Correct 2278 ms 200972 KB Output is correct
23 Correct 2562 ms 203808 KB Output is correct
24 Correct 4521 ms 202964 KB Output is correct
25 Correct 4623 ms 206952 KB Output is correct
26 Correct 4376 ms 203000 KB Output is correct
27 Correct 6190 ms 222252 KB Output is correct
28 Correct 887 ms 204532 KB Output is correct
29 Correct 4403 ms 202800 KB Output is correct
30 Correct 4374 ms 202228 KB Output is correct
31 Correct 4369 ms 202996 KB Output is correct
32 Correct 1022 ms 71552 KB Output is correct
33 Correct 332 ms 68112 KB Output is correct
34 Correct 572 ms 64696 KB Output is correct
35 Correct 611 ms 64824 KB Output is correct
36 Correct 884 ms 65488 KB Output is correct
37 Correct 891 ms 65444 KB Output is correct