oj.uz

Submission #969192

# Submission time Handle Problem Language Result Execution time Memory
969192 2024-04-24T16:19:12 Z biank Factories (JOI14_factories) C++14
100 / 100
 3303 ms 185188 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

using ii = pair<int, int>;
using ll = long long;

template<class x> ostream & operator<<(ostream & out, vector<x> v){
    out<<"[ ";
    for(auto y : v) out<<y<<" ";
    out<<"]";
    return out;
}

const int MAX_N = 5e5 + 9;

int sz[MAX_N];
vector<ii> adj[MAX_N];
bitset<MAX_N> done;

int getSize(int u, int p = -1) {
    sz[u] = 1;
    for (auto [v, w] : adj[u]) {
        if (v != p && !done[v]) {
            sz[u] += getSize(v, u);
        }
    }
    return sz[u];
}

int findCentroid(int u, int size, int p = -1) {
    for (auto [v, w] : adj[u]) {
        if (v != p && !done[v] && sz[v] > size / 2) {
            return findCentroid(v, size, u);
        }
    }
    return u;
}

ll dist[20][MAX_N], best[MAX_N];
int par[MAX_N], height[MAX_N];
int t[MAX_N], timer = 0;
 
void dfs(int u, int h, int p = -1, ll d = 0) {
    dist[h][u] = d;
    for (auto [v, w] : adj[u]) {
        if (v != p && !done[v]) dfs(v, h, u, d + w);
    }
}

void build(int u, int h = 0, int p = -1) {
    int size = getSize(u);
    u = findCentroid(u, size);
    done[u] = true, par[u] = p, height[u] = h;
    dfs(u, h);
    for (auto [v, w] : adj[u]) {
        if (!done[v]) build(v, h + 1, u);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    build(0);
}

void update(int u) {
    for (int v = u, h = height[u]; v != -1; v = par[v], h--) {
        if (t[v] == timer) best[v] = min(best[v], dist[h][u]);
        else best[v] = dist[h][u], t[v] = timer;
    }
}

const ll INF = 1e18;

ll query(int u) {
    ll minDist = INF;
    for (int v = u, h = height[u]; v != -1; v = par[v], h--) {
        if (t[v] == timer) minDist = min(minDist, dist[h][u] + best[v]);
    }
    return minDist;
}

ll Query(int S, int X[], int T, int Y[]) {
    timer++;
    for (int i = 0; i < S; i++) {
        update(X[i]);
    }
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        ans = min(ans, query(Y[i]));
    }
    return ans;
}

Compilation message

factories.cpp: In function 'int getSize(int, int)':
factories.cpp:24:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |     for (auto [v, w] : adj[u]) {
      |               ^
factories.cpp: In function 'int findCentroid(int, int, int)':
factories.cpp:33:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   33 |     for (auto [v, w] : adj[u]) {
      |               ^
factories.cpp: In function 'void dfs(int, int, int, ll)':
factories.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto [v, w] : adj[u]) {
      |               ^
factories.cpp: In function 'void build(int, int, int)':
factories.cpp:57:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |     for (auto [v, w] : adj[u]) {
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55644 KB Output is correct
2 Correct 198 ms 75596 KB Output is correct
3 Correct 217 ms 79700 KB Output is correct
4 Correct 209 ms 79696 KB Output is correct
5 Correct 223 ms 79948 KB Output is correct
6 Correct 142 ms 57172 KB Output is correct
7 Correct 214 ms 77844 KB Output is correct
8 Correct 216 ms 79696 KB Output is correct
9 Correct 232 ms 80208 KB Output is correct
10 Correct 142 ms 57312 KB Output is correct
11 Correct 214 ms 77652 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 55644 KB Output is correct
2 Correct 1187 ms 150760 KB Output is correct
3 Correct 1962 ms 162856 KB Output is correct
4 Correct 407 ms 95528 KB Output is correct
5 Correct 2841 ms 185060 KB Output is correct
6 Correct 2080 ms 163916 KB Output is correct
7 Correct 531 ms 109816 KB Output is correct
8 Correct 219 ms 70592 KB Output is correct
9 Correct 608 ms 113104 KB Output is correct
10 Correct 515 ms 110180 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 55644 KB Output is correct
2 Correct 198 ms 75596 KB Output is correct
3 Correct 217 ms 79700 KB Output is correct
4 Correct 209 ms 79696 KB Output is correct
5 Correct 223 ms 79948 KB Output is correct
6 Correct 142 ms 57172 KB Output is correct
7 Correct 214 ms 77844 KB Output is correct
8 Correct 216 ms 79696 KB Output is correct
9 Correct 232 ms 80208 KB Output is correct
10 Correct 142 ms 57312 KB Output is correct
11 Correct 214 ms 77652 KB Output is correct
12 Correct 9 ms 55644 KB Output is correct
13 Correct 1187 ms 150760 KB Output is correct
14 Correct 1962 ms 162856 KB Output is correct
15 Correct 407 ms 95528 KB Output is correct
16 Correct 2841 ms 185060 KB Output is correct
17 Correct 2080 ms 163916 KB Output is correct
18 Correct 531 ms 109816 KB Output is correct
19 Correct 219 ms 70592 KB Output is correct
20 Correct 608 ms 113104 KB Output is correct
21 Correct 515 ms 110180 KB Output is correct
22 Correct 1545 ms 155248 KB Output is correct
23 Correct 1471 ms 158484 KB Output is correct
24 Correct 2438 ms 167692 KB Output is correct
25 Correct 2534 ms 169736 KB Output is correct
26 Correct 2452 ms 168020 KB Output is correct
27 Correct 3303 ms 185188 KB Output is correct
28 Correct 492 ms 101908 KB Output is correct
29 Correct 2375 ms 167752 KB Output is correct
30 Correct 2396 ms 167316 KB Output is correct
31 Correct 2483 ms 167856 KB Output is correct
32 Correct 640 ms 113316 KB Output is correct
33 Correct 222 ms 70600 KB Output is correct
34 Correct 391 ms 104076 KB Output is correct
35 Correct 406 ms 104260 KB Output is correct
36 Correct 497 ms 108672 KB Output is correct
37 Correct 540 ms 108892 KB Output is correct