oj.uz

Submission #230370

# Submission time Handle Problem Language Result Execution time Memory
230370 2020-05-09T20:27:02 Z arbor Factories (JOI14_factories) C++14
100 / 100
 4969 ms 171996 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define lc (i << 1)
#define rc (i << 1 | 1)
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int MN = 5e5 + 5, LN = 19, MOD = 1e9 + 7, INF = 0x3f3f3f3f, BSZ = 320;
vector<pii> g[MN];
int sz[MN], par[MN], lvl[MN];
ll down[LN][MN]; // dis from a centroid at lvl j, to a node i
bool vis[MN];
ll mn[MN]; // mn dis from centroid i, to any factory of first kind in children
int qid[MN], id = 1;

int get_sz(int u, int p) {
    sz[u] = 1;
    for (pii e : g[u]) if (e.first != p && !vis[e.first])
        sz[u] += get_sz(e.first, u);
    return sz[u];
}

int centroid(int u, int p, int s) {
    for (pii e : g[u]) if (e.first != p && !vis[e.first] && sz[e.first] > s / 2)
        return centroid(e.first, u, s);
    return u;
}

void dfs(int u, int p, ll dis, int d) {
    down[d][u] = dis;
    for (pii e : g[u]) if (e.first != p && !vis[e.first])
            dfs(e.first, u, dis + e.second, d);
}

void go(int u, int p, int d) {
    int s = get_sz(u, -1);
    int c = centroid(u, -1, s);
    par[c] = p;
    lvl[c] = d;
    dfs(c, -1, 0, d);
    vis[c] = true;
    for (pii e : g[c]) {
        if (!vis[e.first]) {
            go(e.first, c, d + 1);
        }
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    memset(down, 0x3f, sizeof(down));
    go(0, -1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        int cur = X[i];
        while (cur != -1) {
            if (qid[cur] != id) qid[cur] = id, mn[cur] = down[lvl[cur]][X[i]];
            else mn[cur] = min(mn[cur], down[lvl[cur]][X[i]]);
            cur = par[cur];
        }
    }
    ll ret = LLONG_MAX;
    for (int i = 0; i < T; i++) {
        int cur = Y[i];
        while (cur != -1) {
            if (qid[cur] == id) ret = min(ret, mn[cur] + down[lvl[cur]][Y[i]]);
            cur = par[cur];
        }
    }
    id++;
    return ret;
}

/*
int main() {
    int N, Q;
    cin >> N >> Q;
    int a[N + 1], b[N + 1], d[N + 1];
    for (int i = 0; i < N - 1; i++) cin >> a[i] >> b[i] >> d[i];
    Init(N, a, b, d);
    for (int i = 0; i < Q; i++) {
        int s, t;
        cin >> s >> t;
        int x[s + 1], y[t + 1];
        for (int j = 0; j < s; j++) cin >> x[j];
        for (int j = 0; j < t; j++) cin >> y[j];
        cout << Query(s, x, t, y) << '\n';
    }
    return 0;
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 87032 KB Output is correct
2 Correct 418 ms 104340 KB Output is correct
3 Correct 436 ms 104288 KB Output is correct
4 Correct 423 ms 104440 KB Output is correct
5 Correct 468 ms 104440 KB Output is correct
6 Correct 327 ms 104312 KB Output is correct
7 Correct 433 ms 104312 KB Output is correct
8 Correct 437 ms 104312 KB Output is correct
9 Correct 455 ms 104568 KB Output is correct
10 Correct 327 ms 104312 KB Output is correct
11 Correct 429 ms 104480 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 86648 KB Output is correct
2 Correct 1891 ms 149068 KB Output is correct
3 Correct 2900 ms 148856 KB Output is correct
4 Correct 767 ms 149340 KB Output is correct
5 Correct 3907 ms 166392 KB Output is correct
6 Correct 3051 ms 150916 KB Output is correct
7 Correct 1014 ms 117240 KB Output is correct
8 Correct 483 ms 118316 KB Output is correct
9 Correct 1155 ms 121208 KB Output is correct
10 Correct 1018 ms 118844 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 87032 KB Output is correct
2 Correct 418 ms 104340 KB Output is correct
3 Correct 436 ms 104288 KB Output is correct
4 Correct 423 ms 104440 KB Output is correct
5 Correct 468 ms 104440 KB Output is correct
6 Correct 327 ms 104312 KB Output is correct
7 Correct 433 ms 104312 KB Output is correct
8 Correct 437 ms 104312 KB Output is correct
9 Correct 455 ms 104568 KB Output is correct
10 Correct 327 ms 104312 KB Output is correct
11 Correct 429 ms 104480 KB Output is correct
12 Correct 45 ms 86648 KB Output is correct
13 Correct 1891 ms 149068 KB Output is correct
14 Correct 2900 ms 148856 KB Output is correct
15 Correct 767 ms 149340 KB Output is correct
16 Correct 3907 ms 166392 KB Output is correct
17 Correct 3051 ms 150916 KB Output is correct
18 Correct 1014 ms 117240 KB Output is correct
19 Correct 483 ms 118316 KB Output is correct
20 Correct 1155 ms 121208 KB Output is correct
21 Correct 1018 ms 118844 KB Output is correct
22 Correct 2495 ms 156044 KB Output is correct
23 Correct 2296 ms 158980 KB Output is correct
24 Correct 3943 ms 157304 KB Output is correct
25 Correct 3784 ms 161172 KB Output is correct
26 Correct 3790 ms 157208 KB Output is correct
27 Correct 4969 ms 171996 KB Output is correct
28 Correct 947 ms 159708 KB Output is correct
29 Correct 4034 ms 157516 KB Output is correct
30 Correct 4019 ms 157024 KB Output is correct
31 Correct 3741 ms 157200 KB Output is correct
32 Correct 1188 ms 121588 KB Output is correct
33 Correct 467 ms 118764 KB Output is correct
34 Correct 747 ms 115344 KB Output is correct
35 Correct 767 ms 115316 KB Output is correct
36 Correct 979 ms 115704 KB Output is correct
37 Correct 983 ms 115704 KB Output is correct