oj.uz

Submission #729664

# Submission time Handle Problem Language Result Execution time Memory
729664 2023-04-24T10:35:29 Z hgmhc Factories (JOI14_factories) C++17
100 / 100
 4411 ms 184336 KB 
#include "factories.h"
#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const ll INF = 1e18;
const int N = 5e5+3, Q = 1e5+3;
int n, q;
vector<ii> adj[N];

namespace centroid_tree {
    int sub[N], par[N], lev[N];
    ll dp[N][20];
    bool erased[N];
    void size_calc(int s, int e = -1) {
        sub[s] = 1;
        for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
            size_calc(u,s), sub[s] += sub[u];
        }
    }
    int centroid(int S, int s, int e = -1) {
        for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
            if (sub[u] > S/2) return centroid(S,u,s);
        }
        return s;
    }
    void dfs(int l, int s, int e = -1, ll d = 0) {
        dp[s][lev[s]-l] = d;
        for (auto [u,w] : adj[s]) if (u != e and not erased[u]) {
            dfs(l,u,s,d+w);
        }
    }
    ll dist[N]{};
    void build(int level = 0, int s = 0, int e = -1) {
        size_calc(s);
        int c = centroid(sub[s],s);
        dist[c] = INF;
        erased[c] = true, par[c] = e;
        lev[c] = level;
        for (auto [u,w] : adj[c]) if (not erased[u]) {
            build(level+1,u,c);
        }
        erased[c] = false;
        for (auto [u,w] : adj[c]) if (not erased[u]) {
            dfs(level,u,c,w);
        }
    }
    ll query(int x) {
        ll res = INF;
        for (int y = x, i = 0; y != -1; y = par[y], ++i) {
            mup(res, dist[y]+dp[x][i]);
        }
        return res;
    }
    void update(int x) {
        for (int y = x, i = 0; y != -1; y = par[y], ++i) {
            mup(dist[y], dp[x][i]);
        }
    }
    void clear(int x) {
        for (int y = x; y != -1; y = par[y]) dist[y] = INF;
    }
};

void Init(int N, int A[], int B[], int D[]) {
    rep(i,0,N-2) {
        auto [u,v,w] = tie(A[i],B[i],D[i]);
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    centroid_tree::build();
}
 
long long Query(int S, int X[], int T, int Y[]) {
    vector<int> x(S);
    ll ans = INF;
    rep(i,0,S-1) centroid_tree::update(X[i]);
    rep(i,0,T-1) mup(ans, centroid_tree::query(Y[i]));
    rep(i,0,S-1) centroid_tree::clear(X[i]);
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12628 KB Output is correct
2 Correct 353 ms 30596 KB Output is correct
3 Correct 315 ms 30652 KB Output is correct
4 Correct 382 ms 30608 KB Output is correct
5 Correct 427 ms 30892 KB Output is correct
6 Correct 305 ms 30644 KB Output is correct
7 Correct 357 ms 30672 KB Output is correct
8 Correct 428 ms 30624 KB Output is correct
9 Correct 305 ms 30968 KB Output is correct
10 Correct 232 ms 30624 KB Output is correct
11 Correct 338 ms 30636 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12348 KB Output is correct
2 Correct 1901 ms 150720 KB Output is correct
3 Correct 2856 ms 152396 KB Output is correct
4 Correct 614 ms 151104 KB Output is correct
5 Correct 3701 ms 181604 KB Output is correct
6 Correct 2721 ms 154488 KB Output is correct
7 Correct 817 ms 58444 KB Output is correct
8 Correct 321 ms 59060 KB Output is correct
9 Correct 892 ms 62720 KB Output is correct
10 Correct 836 ms 59764 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12628 KB Output is correct
2 Correct 353 ms 30596 KB Output is correct
3 Correct 315 ms 30652 KB Output is correct
4 Correct 382 ms 30608 KB Output is correct
5 Correct 427 ms 30892 KB Output is correct
6 Correct 305 ms 30644 KB Output is correct
7 Correct 357 ms 30672 KB Output is correct
8 Correct 428 ms 30624 KB Output is correct
9 Correct 305 ms 30968 KB Output is correct
10 Correct 232 ms 30624 KB Output is correct
11 Correct 338 ms 30636 KB Output is correct
12 Correct 8 ms 12348 KB Output is correct
13 Correct 1901 ms 150720 KB Output is correct
14 Correct 2856 ms 152396 KB Output is correct
15 Correct 614 ms 151104 KB Output is correct
16 Correct 3701 ms 181604 KB Output is correct
17 Correct 2721 ms 154488 KB Output is correct
18 Correct 817 ms 58444 KB Output is correct
19 Correct 321 ms 59060 KB Output is correct
20 Correct 892 ms 62720 KB Output is correct
21 Correct 836 ms 59764 KB Output is correct
22 Correct 2114 ms 158136 KB Output is correct
23 Correct 2215 ms 160904 KB Output is correct
24 Correct 3405 ms 160540 KB Output is correct
25 Correct 3079 ms 164448 KB Output is correct
26 Correct 3121 ms 160708 KB Output is correct
27 Correct 4411 ms 184336 KB Output is correct
28 Correct 1031 ms 161600 KB Output is correct
29 Correct 3380 ms 160160 KB Output is correct
30 Correct 3211 ms 159592 KB Output is correct
31 Correct 3243 ms 160244 KB Output is correct
32 Correct 898 ms 63932 KB Output is correct
33 Correct 359 ms 59620 KB Output is correct
34 Correct 556 ms 56140 KB Output is correct
35 Correct 616 ms 56144 KB Output is correct
36 Correct 765 ms 56768 KB Output is correct
37 Correct 702 ms 56884 KB Output is correct