oj.uz

Submission #894631

# Submission time Handle Problem Language Result Execution time Memory
894631 2023-12-28T14:38:55 Z IWKR Factories (JOI14_factories) C++17
100 / 100
 3135 ms 231208 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

vector<pair<int, int>> adjlist[500001];
int subsz[500001], level[500001], centpar[500001][20];
long long dist[500001][20], ans[500001];
vector<int> v;

void dfs(int x, int p) {
    subsz[x] = 1;
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs(i.first, x);
        subsz[x] += subsz[i.first];
    }
}

int centroid(int x, int p, int treesz) {
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        if (treesz < subsz[i.first] * 2) {
            return centroid(i.first, x, treesz);
        }
    }
    return x;
}

void dfs2(int x, int p, int l, int cent, long long cost) {
    centpar[x][l] = cent;
    dist[x][l] = cost;
    for (auto i: adjlist[x]) {
        if (i.first == p || level[i.first] != 0) {
            continue;
        }
        dfs2(i.first, x, l, cent, cost + i.second);
    }
}

void decomp(int x, int p, int l) {
    dfs(x, -1);
    int cent = centroid(x, -1, subsz[x]);
    level[cent] = l;
    dfs2(cent, -1, l, cent, 0);
    for (auto i: adjlist[cent]) {
        if (level[i.first] == 0) {
            decomp(i.first, cent, l + 1);
        }
    }
}

void update(int x) {
    for (int i = 1; i <= level[x]; i++) {
        ans[centpar[x][i]] = min(ans[centpar[x][i]], dist[x][i]);
        v.push_back(centpar[x][i]);
    }
}

long long query(int x) {
    long long ans2 = LLONG_MAX;
    for (int i = 1; i <= level[x]; i++) {
        if (ans[centpar[x][i]] == LLONG_MAX) {
            continue;
        }
        ans2 = min(ans2, ans[centpar[x][i]] + dist[x][i]);
    }
    return ans2;
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        adjlist[A[i]].push_back({B[i], D[i]});
        adjlist[B[i]].push_back({A[i], D[i]});
    }
    decomp(0, -1, 1);
    for (int i = 0; i < N; i++) {
        ans[i] = LLONG_MAX;
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        update(X[i]);
    }
    long long ans2 = LLONG_MAX;
    for (int i = 0; i < T; i++) {
        ans2 = min(ans2, query(Y[i]));
    }
    for (auto i: v) {
        ans[i] = LLONG_MAX;
    }
    v.clear();
    return ans2;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39656 KB Output is correct
2 Correct 220 ms 55376 KB Output is correct
3 Correct 223 ms 55136 KB Output is correct
4 Correct 213 ms 55516 KB Output is correct
5 Correct 230 ms 55776 KB Output is correct
6 Correct 158 ms 55268 KB Output is correct
7 Correct 221 ms 55256 KB Output is correct
8 Correct 228 ms 55348 KB Output is correct
9 Correct 224 ms 55636 KB Output is correct
10 Correct 181 ms 55124 KB Output is correct
11 Correct 215 ms 55128 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 37208 KB Output is correct
2 Correct 1241 ms 198048 KB Output is correct
3 Correct 2016 ms 200908 KB Output is correct
4 Correct 577 ms 198460 KB Output is correct
5 Correct 2906 ms 229004 KB Output is correct
6 Correct 2088 ms 201932 KB Output is correct
7 Correct 542 ms 87144 KB Output is correct
8 Correct 351 ms 86968 KB Output is correct
9 Correct 661 ms 90576 KB Output is correct
10 Correct 515 ms 87752 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 39656 KB Output is correct
2 Correct 220 ms 55376 KB Output is correct
3 Correct 223 ms 55136 KB Output is correct
4 Correct 213 ms 55516 KB Output is correct
5 Correct 230 ms 55776 KB Output is correct
6 Correct 158 ms 55268 KB Output is correct
7 Correct 221 ms 55256 KB Output is correct
8 Correct 228 ms 55348 KB Output is correct
9 Correct 224 ms 55636 KB Output is correct
10 Correct 181 ms 55124 KB Output is correct
11 Correct 215 ms 55128 KB Output is correct
12 Correct 6 ms 37208 KB Output is correct
13 Correct 1241 ms 198048 KB Output is correct
14 Correct 2016 ms 200908 KB Output is correct
15 Correct 577 ms 198460 KB Output is correct
16 Correct 2906 ms 229004 KB Output is correct
17 Correct 2088 ms 201932 KB Output is correct
18 Correct 542 ms 87144 KB Output is correct
19 Correct 351 ms 86968 KB Output is correct
20 Correct 661 ms 90576 KB Output is correct
21 Correct 515 ms 87752 KB Output is correct
22 Correct 1457 ms 204744 KB Output is correct
23 Correct 1448 ms 208112 KB Output is correct
24 Correct 2300 ms 211184 KB Output is correct
25 Correct 2337 ms 209412 KB Output is correct
26 Correct 2343 ms 203944 KB Output is correct
27 Correct 3135 ms 231208 KB Output is correct
28 Correct 645 ms 204116 KB Output is correct
29 Correct 2146 ms 205684 KB Output is correct
30 Correct 1981 ms 205040 KB Output is correct
31 Correct 1962 ms 205700 KB Output is correct
32 Correct 637 ms 95584 KB Output is correct
33 Correct 303 ms 87864 KB Output is correct
34 Correct 427 ms 85588 KB Output is correct
35 Correct 491 ms 85568 KB Output is correct
36 Correct 597 ms 86248 KB Output is correct
37 Correct 562 ms 86120 KB Output is correct