oj.uz

Submission #603373

# Submission time Handle Problem Language Result Execution time Memory
603373 2022-07-24T05:41:40 Z AA_Surely Factories (JOI14_factories) C++17
100 / 100
 6128 ms 222096 KB 
#include "factories.h"
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 5e5 + 7;
const LL INF = 1e18;
const int LOG = 20;

int n;
int par[N], sz[N];
int up[N][LOG], height[N];
bool vis[N];
LL dtr[N], opt[N], udi[N][LOG];
VPII adj[N];

int getSz(int now, int p = -1) {
    sz[now] = 1;
    for(const auto &[on, v] : adj[now]) if (on != p && !vis[on]) sz[now] += getSz(on, now);
    return sz[now];
}

int getCent(int now, int p, int nn) {
    for(const auto &[on, v] : adj[now]) 
        if (on != p && !vis[on] && sz[on] > nn / 2) 
            return getCent(on, now, nn);
    return now;
}

void decomp(int now, int p = -1) {
    getSz(now);
    int c = getCent(now, -1, sz[now]);

    par[c] = p;
    vis[c] = 1;

    for(auto [on, w] : adj[c]) if (!vis[on]) decomp(on, c);
    return;
}

void dfs(int now, int p = -1, int h = 0, LL dist = 0) {
    up[now][0] = p;
    height[now] = h;
    dtr[now] = dist;
    for(auto [on, w] : adj[now]) if (on != p) dfs(on, now, h + 1, dist + w);
    return;
}

int lca(int a, int b) {
    if (height[a] < height[b]) swap(a, b);
    R0F(i, LOG) if (height[a] - (1 << i) >= height[b]) a = up[a][i];
    if (a == b) return a;
    R0F(i, LOG) if (up[a][i] != up[b][i])
        a = up[a][i], b = up[b][i];
    return up[a][0];
}

LL dist(int a, int b) {
    int z = lca(a, b);
    return dtr[a] + dtr[b] - 2LL * dtr[z];
}

void precalc() {
    F0R(i, n) {
        int cnt = 0;
        int v = i;
        while(v != -1) {
            udi[i][cnt] = dist(v, i);
            v = par[v];
            cnt++;
        }
    }

    return;
}

void Init(int nn, int A[], int B[], int D[]) {
    n = nn;
    F0R(i, n - 1) {
        adj[ A[i] ].PB({B[i], D[i]});
        adj[ B[i] ].PB({A[i], D[i]});
    }

    decomp(0);
    dfs(0);

    up[n][0] = n;
    FOR(k, 1, LOG) F0R(i, n + 1)
        up[i][k] = up[ up[i][k - 1] ][k - 1];
    
    precalc();
    fill(opt, opt + n, INF);
    return;
}

void add(int v) {
    int now = v;
    int cnt = 0;
    while(now != -1) {
        opt[now] = min(opt[now], udi[v][cnt]);
        now = par[now];
        cnt++;
    }

    return;
}

LL getMin(int v) {
    LL ret = INF;
    int now = v;
    int cnt = 0;
    while(now != -1) {
        ret = min(ret, opt[now] + udi[v][cnt]);
        now = par[now];
        cnt++;
    }

    return ret;
}

void rem(int v) {
    while(v != -1) {
        opt[v] = INF;
        v = par[v];
    }
}

LL Query(int s, int xs[], int t, int ys[]) {
    F0R(i, s) add(xs[i]);
    LL ans = INF;
    F0R(i, t) ans = min(ans, getMin(ys[i]));
    F0R(i, s) rem(xs[i]);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 234 ms 21584 KB Output is correct
3 Correct 324 ms 21632 KB Output is correct
4 Correct 263 ms 21672 KB Output is correct
5 Correct 279 ms 21828 KB Output is correct
6 Correct 183 ms 21672 KB Output is correct
7 Correct 283 ms 21596 KB Output is correct
8 Correct 262 ms 21628 KB Output is correct
9 Correct 300 ms 21896 KB Output is correct
10 Correct 174 ms 21684 KB Output is correct
11 Correct 258 ms 21612 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12372 KB Output is correct
2 Correct 1919 ms 175020 KB Output is correct
3 Correct 4043 ms 176600 KB Output is correct
4 Correct 677 ms 175884 KB Output is correct
5 Correct 5635 ms 199352 KB Output is correct
6 Correct 4096 ms 196764 KB Output is correct
7 Correct 849 ms 66836 KB Output is correct
8 Correct 311 ms 67740 KB Output is correct
9 Correct 1086 ms 70528 KB Output is correct
10 Correct 868 ms 68340 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12500 KB Output is correct
2 Correct 234 ms 21584 KB Output is correct
3 Correct 324 ms 21632 KB Output is correct
4 Correct 263 ms 21672 KB Output is correct
5 Correct 279 ms 21828 KB Output is correct
6 Correct 183 ms 21672 KB Output is correct
7 Correct 283 ms 21596 KB Output is correct
8 Correct 262 ms 21628 KB Output is correct
9 Correct 300 ms 21896 KB Output is correct
10 Correct 174 ms 21684 KB Output is correct
11 Correct 258 ms 21612 KB Output is correct
12 Correct 9 ms 12372 KB Output is correct
13 Correct 1919 ms 175020 KB Output is correct
14 Correct 4043 ms 176600 KB Output is correct
15 Correct 677 ms 175884 KB Output is correct
16 Correct 5635 ms 199352 KB Output is correct
17 Correct 4096 ms 196764 KB Output is correct
18 Correct 849 ms 66836 KB Output is correct
19 Correct 311 ms 67740 KB Output is correct
20 Correct 1086 ms 70528 KB Output is correct
21 Correct 868 ms 68340 KB Output is correct
22 Correct 2217 ms 201068 KB Output is correct
23 Correct 2216 ms 203704 KB Output is correct
24 Correct 4407 ms 202792 KB Output is correct
25 Correct 4618 ms 206780 KB Output is correct
26 Correct 4754 ms 202972 KB Output is correct
27 Correct 6128 ms 222096 KB Output is correct
28 Correct 788 ms 204752 KB Output is correct
29 Correct 4482 ms 202636 KB Output is correct
30 Correct 4402 ms 202196 KB Output is correct
31 Correct 4296 ms 202704 KB Output is correct
32 Correct 1010 ms 71512 KB Output is correct
33 Correct 319 ms 68100 KB Output is correct
34 Correct 542 ms 64904 KB Output is correct
35 Correct 569 ms 64788 KB Output is correct
36 Correct 798 ms 65252 KB Output is correct
37 Correct 869 ms 65264 KB Output is correct