oj.uz

Submission #373163

# Submission time Handle Problem Language Result Execution time Memory
373163 2021-03-03T14:45:14 Z BartolM Factories (JOI14_factories) C++17
100 / 100
 4848 ms 131484 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <int, pii> pip;
typedef pair <pii, int> ppi;
typedef pair <ll, ll> pll;

const int INF=0x3f3f3f3f;
const ll MAX=(ll)INF*INF;
const int MAXN=5e5+5;
const int LOG=20;
const int OFF=(1<<19);

int n, dtime=0, ind;
ll dist[MAXN];
int par[LOG][MAXN], dep[MAXN], L[MAXN], R[MAXN];
vector <pii> ls[MAXN];
ll da[MAXN], db[MAXN];
vector <int> v;

int cmp(int a, int b) {
    return L[a]<L[b];
}

void dfs(int node, int rod, ll d) {
    par[0][node]=rod;
    dist[node]=d;
    dep[node]=dep[rod]+1;
    L[node]=dtime++;
//    printf("node: %d, dist: %lld, dep: %d, par: %d\n", node, dist[node], dep[node], rod);
    for (pii sus:ls[node]) if (sus.X!=rod) dfs(sus.X, node, d+sus.Y);
    R[node]=dtime;
}

void build() {
    for (int i=1; i<LOG; ++i) {
        for (int j=0; j<n; ++j) {
            par[i][j]=par[i-1][par[i-1][j]];
        }
    }
}

int lca(int x, int y) {
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=LOG-1; i>=0; --i) {
        if (dep[x]-(1<<i)>=dep[y]) x=par[i][x];
    }
    if (x==y) return x;
    for (int i=LOG-1; i>=0; --i) {
        if (par[i][x]!=par[i][y]) x=par[i][x], y=par[i][y];
    }
    return par[0][x];
}

void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0; i<n-1; ++i) {
        ls[A[i]].pb(mp(B[i], D[i]));
        ls[B[i]].pb(mp(A[i], D[i]));
    }
    dfs(0, 0, 0);
    build();
    for (int i=0; i<n; ++i) da[i]=db[i]=MAX;
}

ll rek() {
    ll ret=MAX;
    int node=v[ind++];
    while (ind<(int)v.size() && L[v[ind]]>=L[node] && L[v[ind]]<R[node]) {
        int sus=v[ind];
        ret=min(ret, rek());
        da[node]=min(da[node], da[sus]+dist[sus]-dist[node]);
        db[node]=min(db[node], db[sus]+dist[sus]-dist[node]);
    }
    ret=min(ret, da[node]+db[node]);
    return ret;
}

ll Query(int S, int x[], int T, int y[]) {
    v.clear();
    for (int i=0; i<S; ++i) {
        v.pb(x[i]);
        da[x[i]]=0;
    }
    for (int i=0; i<T; ++i) {
        v.pb(y[i]);
        db[y[i]]=0;
    }

    sort(v.begin(), v.end(), cmp);
    for (int i=1; i<S+T; ++i) {
        int lc=lca(v[i-1], v[i]);
        v.pb(lc);
    }


    v.pb(0);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    sort(v.begin(), v.end(), cmp);
//    for (int x:v) printf("%d ", x);
//    printf("\n");

    ind=0;
    ll sol=rek();

    for (int x:v) da[x]=db[x]=MAX;
    return sol;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12652 KB Output is correct
2 Correct 1192 ms 21148 KB Output is correct
3 Correct 1191 ms 21356 KB Output is correct
4 Correct 1174 ms 21316 KB Output is correct
5 Correct 979 ms 21356 KB Output is correct
6 Correct 959 ms 21100 KB Output is correct
7 Correct 1222 ms 21380 KB Output is correct
8 Correct 1156 ms 21224 KB Output is correct
9 Correct 981 ms 21612 KB Output is correct
10 Correct 982 ms 21232 KB Output is correct
11 Correct 1181 ms 21368 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12396 KB Output is correct
2 Correct 2056 ms 100560 KB Output is correct
3 Correct 2912 ms 101820 KB Output is correct
4 Correct 1434 ms 101204 KB Output is correct
5 Correct 2603 ms 124560 KB Output is correct
6 Correct 3187 ms 103348 KB Output is correct
7 Correct 3061 ms 38472 KB Output is correct
8 Correct 1592 ms 39076 KB Output is correct
9 Correct 2240 ms 41752 KB Output is correct
10 Correct 3028 ms 39660 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12652 KB Output is correct
2 Correct 1192 ms 21148 KB Output is correct
3 Correct 1191 ms 21356 KB Output is correct
4 Correct 1174 ms 21316 KB Output is correct
5 Correct 979 ms 21356 KB Output is correct
6 Correct 959 ms 21100 KB Output is correct
7 Correct 1222 ms 21380 KB Output is correct
8 Correct 1156 ms 21224 KB Output is correct
9 Correct 981 ms 21612 KB Output is correct
10 Correct 982 ms 21232 KB Output is correct
11 Correct 1181 ms 21368 KB Output is correct
12 Correct 11 ms 12396 KB Output is correct
13 Correct 2056 ms 100560 KB Output is correct
14 Correct 2912 ms 101820 KB Output is correct
15 Correct 1434 ms 101204 KB Output is correct
16 Correct 2603 ms 124560 KB Output is correct
17 Correct 3187 ms 103348 KB Output is correct
18 Correct 3061 ms 38472 KB Output is correct
19 Correct 1592 ms 39076 KB Output is correct
20 Correct 2240 ms 41752 KB Output is correct
21 Correct 3028 ms 39660 KB Output is correct
22 Correct 3550 ms 102764 KB Output is correct
23 Correct 3466 ms 105020 KB Output is correct
24 Correct 3652 ms 104936 KB Output is correct
25 Correct 3899 ms 108124 KB Output is correct
26 Correct 4642 ms 104204 KB Output is correct
27 Correct 3085 ms 131484 KB Output is correct
28 Correct 2584 ms 114892 KB Output is correct
29 Correct 4809 ms 111580 KB Output is correct
30 Correct 4804 ms 111060 KB Output is correct
31 Correct 4848 ms 111600 KB Output is correct
32 Correct 1684 ms 57704 KB Output is correct
33 Correct 1756 ms 54444 KB Output is correct
34 Correct 2350 ms 50064 KB Output is correct
35 Correct 2304 ms 50160 KB Output is correct
36 Correct 2630 ms 50544 KB Output is correct
37 Correct 2602 ms 50540 KB Output is correct