oj.uz

Submission #274869

# Submission time Handle Problem Language Result Execution time Memory
274869 2020-08-19T18:30:35 Z smax Factories (JOI14_factories) C++17
100 / 100
 7971 ms 224112 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define MAXN 500005

const long long INF = 1e18;

struct CentroidDecomposition {
    vector<int> sub, par;
    vector<bool> visited;
    vector<vector<int>> adj;

    CentroidDecomposition() {}

    CentroidDecomposition(int n) : sub(n), par(n), visited(n), adj(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void build(int u = 0, int p = -1) {
        u = centroid(u, p, dfs(u, p));
        par[u] = p;
        visited[u] = true;
        for (int v : adj[u])
            if (!visited[v])
                build(v, u);
    }

    int dfs(int u, int p) {
        sub[u] = 1;
        for (int v : adj[u])
            if (v != p && !visited[v])
                sub[u] += dfs(v, u);
        return sub[u];
    }

    int centroid(int u, int p, int sz) {
        for (int v : adj[u])
            if (v != p && !visited[v] && sub[v] > sz / 2)
                return centroid(v, u, sz);
        return u;
    }

    int operator [] (int i) const {
        return par[i];
    }
};

struct RMQ {
    vector<long long> a;
    vector<vector<int>> spt;

    void init(int n, long long *_a) {
        a.resize(n);
        spt.assign(1, vector<int>(n));
        for (int i=0; i<n; i++) {
            a[i] = _a[i];
            spt[0][i] = i;
        }

        for (int j=1; 1<<j<=n; j++) {
            spt.emplace_back(n - (1 << j) + 1);
            for (int i=0; i+(1<<j)<=n; i++) {
                if (a[spt[j-1][i]] < a[spt[j-1][i+(1<<(j-1))]])
                    spt[j][i] = spt[j-1][i];
                else
                    spt[j][i] = spt[j-1][i+(1<<(j-1))];
            }
        }
    }

    int query(int i, int j) {
        int k = 31 - __builtin_clz(j - i + 1);
        if (a[spt[k][i]] < a[spt[k][j-(1<<k)+1]])
            return spt[k][i];
        else
            return spt[k][j-(1<<k)+1];
    }
};

int idx, ti[MAXN], node[2*MAXN];
long long depth[2*MAXN];
vector<pair<int, int>> adj[MAXN];
RMQ rmq;

void dfs(int u, int p, long long d) {
    ti[u] = idx;
    node[idx] = u;
    depth[idx++] = d;
    for (auto &e : adj[u])
        if (e.first != p) {
            dfs(e.first, u, d + e.second);
            node[idx] = u;
            depth[idx++] = d;
        }
}

int lca(int u, int v) {
    if (ti[u] > ti[v])
        swap(u, v);
    return node[rmq.query(ti[u], ti[v])];
}

long long dist(int u, int v) {
    return depth[ti[u]] + depth[ti[v]] - 2 * depth[ti[lca(u, v)]];
}

void preprocess() {
    idx = 0;
    dfs(0, -1, 0);
    rmq.init(idx, depth);
}

long long ans[MAXN];
CentroidDecomposition cd;

void Init(int N, int A[], int B[], int D[]) {
    cd = CentroidDecomposition(N);
    for (int i=0; i<N-1; i++) {
        cd.addEdge(A[i], B[i]);
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    cd.build();
    preprocess();
    for (int i=0; i<N; i++)
        ans[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; i++) {
        int u = X[i];
        while (u != -1) {
            ans[u] = min(ans[u], dist(X[i], u));
            u = cd[u];
        }
    }
    long long ret = INF;
    for (int i=0; i<T; i++) {
        int u = Y[i];
        while (u != -1) {
            ret = min(ret, ans[u] + dist(Y[i], u));
            u = cd[u];
        }
    }
    for (int i=0; i<S; i++) {
        int u = X[i];
        while (u != -1) {
            ans[u] = INF;
            u = cd[u];
        }
    }
    return ret;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12672 KB Output is correct
2 Correct 592 ms 30864 KB Output is correct
3 Correct 764 ms 30840 KB Output is correct
4 Correct 788 ms 30840 KB Output is correct
5 Correct 810 ms 31352 KB Output is correct
6 Correct 351 ms 30968 KB Output is correct
7 Correct 765 ms 31116 KB Output is correct
8 Correct 799 ms 30968 KB Output is correct
9 Correct 816 ms 31224 KB Output is correct
10 Correct 361 ms 30840 KB Output is correct
11 Correct 803 ms 30968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12416 KB Output is correct
2 Correct 3277 ms 193120 KB Output is correct
3 Correct 4353 ms 195120 KB Output is correct
4 Correct 1360 ms 195588 KB Output is correct
5 Correct 5736 ms 224112 KB Output is correct
6 Correct 4758 ms 196992 KB Output is correct
7 Correct 2601 ms 65136 KB Output is correct
8 Correct 757 ms 66388 KB Output is correct
9 Correct 3085 ms 69672 KB Output is correct
10 Correct 2708 ms 66720 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12672 KB Output is correct
2 Correct 592 ms 30864 KB Output is correct
3 Correct 764 ms 30840 KB Output is correct
4 Correct 788 ms 30840 KB Output is correct
5 Correct 810 ms 31352 KB Output is correct
6 Correct 351 ms 30968 KB Output is correct
7 Correct 765 ms 31116 KB Output is correct
8 Correct 799 ms 30968 KB Output is correct
9 Correct 816 ms 31224 KB Output is correct
10 Correct 361 ms 30840 KB Output is correct
11 Correct 803 ms 30968 KB Output is correct
12 Correct 10 ms 12416 KB Output is correct
13 Correct 3277 ms 193120 KB Output is correct
14 Correct 4353 ms 195120 KB Output is correct
15 Correct 1360 ms 195588 KB Output is correct
16 Correct 5736 ms 224112 KB Output is correct
17 Correct 4758 ms 196992 KB Output is correct
18 Correct 2601 ms 65136 KB Output is correct
19 Correct 757 ms 66388 KB Output is correct
20 Correct 3085 ms 69672 KB Output is correct
21 Correct 2708 ms 66720 KB Output is correct
22 Correct 4576 ms 182008 KB Output is correct
23 Correct 4699 ms 184416 KB Output is correct
24 Correct 6325 ms 183856 KB Output is correct
25 Correct 6472 ms 187420 KB Output is correct
26 Correct 6588 ms 184076 KB Output is correct
27 Correct 7971 ms 207400 KB Output is correct
28 Correct 1791 ms 185612 KB Output is correct
29 Correct 6305 ms 182576 KB Output is correct
30 Correct 6383 ms 182064 KB Output is correct
31 Correct 6298 ms 182704 KB Output is correct
32 Correct 2756 ms 70548 KB Output is correct
33 Correct 710 ms 66852 KB Output is correct
34 Correct 1960 ms 63112 KB Output is correct
35 Correct 2003 ms 63216 KB Output is correct
36 Correct 2655 ms 63548 KB Output is correct
37 Correct 2587 ms 63592 KB Output is correct