oj.uz

Submission #591565

# Submission time Handle Problem Language Result Execution time Memory
591565 2022-07-07T15:12:01 Z Do_you_copy Factories (JOI14_factories) C++17
100 / 100
 3539 ms 178940 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 5e5 + 2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, q;
int a[maxN], b[maxN];
int par[maxN];
int depth[maxN];
int subtree_size[maxN];
ll dist[maxN][20];
ll ans[maxN];
bool visited[maxN];
vector <pii> adj[maxN];

void centroid_dfs(int u, int p){
    subtree_size[u] = 1;
    for (const auto &i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        centroid_dfs(i.fi, u);
        subtree_size[u] += subtree_size[i.fi];
    }
}

int find_centroid(int u, int p, int sz){
    for (const auto &i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        if (subtree_size[i.fi] > sz / 2) return find_centroid(i.fi, u, sz);
    }
    return u;
}

void find_distance(int u, int p, int c, ll d = 0){
    for (const auto &i: adj[u]){
        if (visited[i.fi] || i.fi == p) continue;
        dist[i.fi][c] = d + i.se;
        find_distance(i.fi, u, c, d + i.se);
    }
}

void update(int u){
    int v = u;
    while (v){
        ans[v] = min(ans[v], dist[u][depth[v]]);
        v = par[v];
    }
}

ll get(int u){
    ll res = inf;
    int v = u;
    while (v){
        res = min(res, ans[v] + dist[u][depth[v]]);
        v = par[v];
    }
    return res;
}

void reupdate(int u){
    int v = u;
    while (v){
        ans[v] = inf;
        v = par[v];
    }
}
int build_centroid(int u, int low){
    centroid_dfs(u, -1);
    int centroid = find_centroid(u, -1, subtree_size[u]);
    visited[centroid] = 1;
    depth[centroid] = low;
    find_distance(centroid, -1, low);
    for (const auto &i: adj[centroid]){
        if (visited[i.fi]) continue;
        par[build_centroid(i.fi, low + 1)] = centroid;
    }
    return centroid;
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    memset(ans, 0x3f, sizeof(ans));
    for (int i = 0; i < n - 1; ++i){
        int u, v, w;
        u = A[i], v = B[i], w = D[i];
        adj[u + 1].pb({v + 1, w});
        adj[v + 1].pb({u + 1, w});
    }
    par[build_centroid(1, 1)] = 0;
}

ll Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < S; ++i){
        update(X[i] + 1);
    }
    ll answer = inf;
    for (int i = 0; i < T; ++i){
        answer = min(answer, get(Y[i] + 1));
    }
    for (int i = 0; i < S; ++i){
        reupdate(X[i] + 1);
    }
  return answer;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16340 KB Output is correct
2 Correct 273 ms 34564 KB Output is correct
3 Correct 297 ms 34496 KB Output is correct
4 Correct 298 ms 34548 KB Output is correct
5 Correct 287 ms 34712 KB Output is correct
6 Correct 187 ms 34472 KB Output is correct
7 Correct 279 ms 34544 KB Output is correct
8 Correct 292 ms 34640 KB Output is correct
9 Correct 292 ms 34708 KB Output is correct
10 Correct 188 ms 34456 KB Output is correct
11 Correct 286 ms 34448 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16212 KB Output is correct
2 Correct 1523 ms 150852 KB Output is correct
3 Correct 2260 ms 151516 KB Output is correct
4 Correct 550 ms 151328 KB Output is correct
5 Correct 3122 ms 174984 KB Output is correct
6 Correct 2338 ms 153608 KB Output is correct
7 Correct 710 ms 61608 KB Output is correct
8 Correct 318 ms 62304 KB Output is correct
9 Correct 848 ms 65800 KB Output is correct
10 Correct 730 ms 62780 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16340 KB Output is correct
2 Correct 273 ms 34564 KB Output is correct
3 Correct 297 ms 34496 KB Output is correct
4 Correct 298 ms 34548 KB Output is correct
5 Correct 287 ms 34712 KB Output is correct
6 Correct 187 ms 34472 KB Output is correct
7 Correct 279 ms 34544 KB Output is correct
8 Correct 292 ms 34640 KB Output is correct
9 Correct 292 ms 34708 KB Output is correct
10 Correct 188 ms 34456 KB Output is correct
11 Correct 286 ms 34448 KB Output is correct
12 Correct 8 ms 16212 KB Output is correct
13 Correct 1523 ms 150852 KB Output is correct
14 Correct 2260 ms 151516 KB Output is correct
15 Correct 550 ms 151328 KB Output is correct
16 Correct 3122 ms 174984 KB Output is correct
17 Correct 2338 ms 153608 KB Output is correct
18 Correct 710 ms 61608 KB Output is correct
19 Correct 318 ms 62304 KB Output is correct
20 Correct 848 ms 65800 KB Output is correct
21 Correct 730 ms 62780 KB Output is correct
22 Correct 1676 ms 157960 KB Output is correct
23 Correct 1772 ms 160752 KB Output is correct
24 Correct 2787 ms 159888 KB Output is correct
25 Correct 2676 ms 163592 KB Output is correct
26 Correct 2709 ms 159888 KB Output is correct
27 Correct 3539 ms 178940 KB Output is correct
28 Correct 678 ms 161484 KB Output is correct
29 Correct 2790 ms 159568 KB Output is correct
30 Correct 2724 ms 159324 KB Output is correct
31 Correct 2670 ms 159668 KB Output is correct
32 Correct 863 ms 66124 KB Output is correct
33 Correct 318 ms 62728 KB Output is correct
34 Correct 535 ms 59304 KB Output is correct
35 Correct 577 ms 59212 KB Output is correct
36 Correct 713 ms 59724 KB Output is correct
37 Correct 719 ms 60108 KB Output is correct