oj.uz

Submission #464595

# Submission time Handle Problem Language Result Execution time Memory
464595 2021-08-13T13:51:52 Z TruaShamu Factories (JOI14_factories) C++11
100 / 100
 5543 ms 371832 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define pb push_back
#define LINF 0x3f3f3f3f3f3f3f3f
#define endl '\n'
#define ll long long
#define f first
#define s second
using namespace std;
typedef pair<ll, ll> pii;

const int MAXN = 5e5 + 5;

ll sub_size[MAXN], visited[MAXN], best[MAXN];
vector<pii> adj[MAXN], dis[MAXN];

// Find subtree size.
int subSize(int cur, int par) {
    sub_size[cur] = 1;
    for (pii next : adj[cur])
        if (next.f != par && !visited[next.f])
            sub_size[cur] += subSize(next.f, cur);
    return sub_size[cur];
}
// Return the centroid.
int findCentroid(int cur, int par, int N) {
    for (pii next : adj[cur]) {
        if (next.f != par && !visited[next.f] && sub_size[next.f] > N / 2) {
            return findCentroid(next.f, cur, N);
        }
    }
    return cur;
}

void getDis(int cur, int par, int c, ll dist) {
    dis[cur].pb({ c, dist });
    for (pii next : adj[cur]) {
        if (next.f != par && !visited[next.f]) {
            getDis(next.f, cur, c, dist + next.s);
        }
    }
}

void build(int cur) {
    int centroid = findCentroid(cur, -1, subSize(cur, -1));
    getDis(centroid, -1, centroid, 0);
    visited[centroid] = 1;

    for (pii next : adj[centroid]) {
        if (!visited[next.f]) {
            build(next.f);
        }
    }
}



// Initialize function
void Init(int n, int a[], int b[], int c[]) {
    // Read edges
    for (int i = 0; i < n - 1; i++) {
        adj[a[i]].pb({ b[i], c[i] });
        adj[b[i]].pb({ a[i], c[i] });
    }
    build(0);
    fill(best, best + MAXN, LINF);
}

// Process queries
ll Query(int len1, int x[], int len2, int y[]) {

    ll ans = LINF;
    for (int u = 0; u < len1; u++) {
        for (pii i : dis[x[u]]) {
            best[i.f] = min(best[i.f], i.s);
        }
    }
    for (int u = 0; u < len2; u++) {
        for (pii i : dis[y[u]]) {
            ans = min(ans, best[i.f] + i.s);
        }
    }
    for (int u = 0; u < len1; u++) {
        for (pii i : dis[x[u]]) {
            best[i.f] = LINF;
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28232 KB Output is correct
2 Correct 352 ms 46276 KB Output is correct
3 Correct 373 ms 46804 KB Output is correct
4 Correct 402 ms 46760 KB Output is correct
5 Correct 401 ms 47264 KB Output is correct
6 Correct 281 ms 45880 KB Output is correct
7 Correct 368 ms 46788 KB Output is correct
8 Correct 375 ms 46840 KB Output is correct
9 Correct 401 ms 47144 KB Output is correct
10 Correct 305 ms 45876 KB Output is correct
11 Correct 382 ms 46848 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 27852 KB Output is correct
2 Correct 2588 ms 219792 KB Output is correct
3 Correct 4163 ms 289816 KB Output is correct
4 Correct 1075 ms 113448 KB Output is correct
5 Correct 4941 ms 365292 KB Output is correct
6 Correct 4090 ms 291144 KB Output is correct
7 Correct 1334 ms 86964 KB Output is correct
8 Correct 542 ms 64136 KB Output is correct
9 Correct 1360 ms 101204 KB Output is correct
10 Correct 1253 ms 88432 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 28232 KB Output is correct
2 Correct 352 ms 46276 KB Output is correct
3 Correct 373 ms 46804 KB Output is correct
4 Correct 402 ms 46760 KB Output is correct
5 Correct 401 ms 47264 KB Output is correct
6 Correct 281 ms 45880 KB Output is correct
7 Correct 368 ms 46788 KB Output is correct
8 Correct 375 ms 46840 KB Output is correct
9 Correct 401 ms 47144 KB Output is correct
10 Correct 305 ms 45876 KB Output is correct
11 Correct 382 ms 46848 KB Output is correct
12 Correct 17 ms 27852 KB Output is correct
13 Correct 2588 ms 219792 KB Output is correct
14 Correct 4163 ms 289816 KB Output is correct
15 Correct 1075 ms 113448 KB Output is correct
16 Correct 4941 ms 365292 KB Output is correct
17 Correct 4090 ms 291144 KB Output is correct
18 Correct 1334 ms 86964 KB Output is correct
19 Correct 542 ms 64136 KB Output is correct
20 Correct 1360 ms 101204 KB Output is correct
21 Correct 1253 ms 88432 KB Output is correct
22 Correct 3379 ms 225024 KB Output is correct
23 Correct 3383 ms 230012 KB Output is correct
24 Correct 4751 ms 297512 KB Output is correct
25 Correct 5166 ms 301480 KB Output is correct
26 Correct 4696 ms 298248 KB Output is correct
27 Correct 5543 ms 371832 KB Output is correct
28 Correct 1532 ms 123872 KB Output is correct
29 Correct 4787 ms 297588 KB Output is correct
30 Correct 4846 ms 297856 KB Output is correct
31 Correct 4780 ms 297744 KB Output is correct
32 Correct 1565 ms 101704 KB Output is correct
33 Correct 654 ms 64648 KB Output is correct
34 Correct 1033 ms 79584 KB Output is correct
35 Correct 1037 ms 80248 KB Output is correct
36 Correct 1274 ms 85524 KB Output is correct
37 Correct 1255 ms 85444 KB Output is correct