oj.uz

Submission #945209

# Submission time Handle Problem Language Result Execution time Memory
945209 2024-03-13T14:18:50 Z VMaksimoski008 Factories (JOI14_factories) C++14
100 / 100
 4121 ms 361496 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 5e5 + 5;
const double eps = 1e-9;

int n, del[maxn], sub[maxn];
ll dist[maxn];
vector<vector<pll> > graph(maxn), anc(maxn);

int get_sub(int u, int p) {
    sub[u] = 1;
    for(auto &[v, _] : graph[u]) {
        if(v == p || del[v]) continue;
        sub[u] += get_sub(v, u);
    }
    return sub[u];
}

int get_cen(int u, int p, int sz) {
    for(auto &[v, _] : graph[u]) {
        if(v == p || del[v]) continue;
        if(2 * sub[v] > sz) return get_cen(v, u, sz);
    }
    return u;
}

void get_dist(int u, int cen, int p, ll d) {
    for(auto &[v, w] : graph[u]) {
        if(v == p || del[v]) continue;
        get_dist(v, cen, u, d + w);
    }
    anc[u].push_back({ cen, d });
}

void update(int u, int t) {
    for(auto &[v, d] : anc[u]) {
        if(t) dist[v] = min(dist[v], d);
        else dist[v] = 1e18;
    }
    dist[u] = (t ? 0 : 1e18);
}

ll query(int u) {
    ll ans = dist[u];
    for(auto &[v, d] : anc[u])
        ans = min(ans, d + dist[v]);
    return ans;
}

void build(int u) {
    int cen = get_cen(u, -1, get_sub(u, -1));

    for(auto &[v, w] : graph[cen]) {
        if(del[v]) continue;
        get_dist(v, cen, cen, w);
    }

    del[cen] = 1;

    for(auto &[v, w] : graph[cen]) {
        if(del[v]) continue;
        build(v);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<n-1; i++) {
        graph[A[i]].push_back({ B[i], D[i] });
        graph[B[i]].push_back({ A[i], D[i] });
    }
    for(int i=0; i<n; i++) dist[i] = 1e18;
    build(0);
}

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

// int main() {
//     int N, Q;
//     cin >> N >> Q;
//     int A[N-1], B[N-1], D[N-1];

//     for(int i=0; i<N-1; i++) {
//         cin >> A[i] >> B[i] >> D[i];
//     }

//     Init(N, A, B, D);

//     while(Q--) {
//         int S, T;
//         cin >> S >> T;
//         int X[S], Y[T];

//         for(int i=0; i<S; i++) cin >> X[i];
//         for(int i=0; i<T; i++) cin >> Y[i];

//         cout << Query(S, X, T, Y) << '\n';
//     }

//     return 0;
// }

Compilation message

factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:27:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   27 |     for(auto &[v, _] : graph[u]) {
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:35:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for(auto &[v, _] : graph[u]) {
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:43:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |     for(auto &[v, w] : graph[u]) {
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto &[v, d] : anc[u]) {
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:60:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |     for(auto &[v, d] : anc[u])
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:68:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |     for(auto &[v, w] : graph[cen]) {
      |               ^
factories.cpp:75:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |     for(auto &[v, w] : graph[cen]) {
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 46692 KB Output is correct
2 Correct 220 ms 58884 KB Output is correct
3 Correct 205 ms 59276 KB Output is correct
4 Correct 207 ms 59392 KB Output is correct
5 Correct 219 ms 59928 KB Output is correct
6 Correct 152 ms 58492 KB Output is correct
7 Correct 256 ms 59420 KB Output is correct
8 Correct 205 ms 59396 KB Output is correct
9 Correct 222 ms 59928 KB Output is correct
10 Correct 159 ms 58464 KB Output is correct
11 Correct 205 ms 59256 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 46428 KB Output is correct
2 Correct 1719 ms 216328 KB Output is correct
3 Correct 2595 ms 262128 KB Output is correct
4 Correct 549 ms 112304 KB Output is correct
5 Correct 3358 ms 355832 KB Output is correct
6 Correct 2746 ms 262744 KB Output is correct
7 Correct 666 ms 98812 KB Output is correct
8 Correct 231 ms 73664 KB Output is correct
9 Correct 775 ms 104436 KB Output is correct
10 Correct 653 ms 99424 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 46692 KB Output is correct
2 Correct 220 ms 58884 KB Output is correct
3 Correct 205 ms 59276 KB Output is correct
4 Correct 207 ms 59392 KB Output is correct
5 Correct 219 ms 59928 KB Output is correct
6 Correct 152 ms 58492 KB Output is correct
7 Correct 256 ms 59420 KB Output is correct
8 Correct 205 ms 59396 KB Output is correct
9 Correct 222 ms 59928 KB Output is correct
10 Correct 159 ms 58464 KB Output is correct
11 Correct 205 ms 59256 KB Output is correct
12 Correct 11 ms 46428 KB Output is correct
13 Correct 1719 ms 216328 KB Output is correct
14 Correct 2595 ms 262128 KB Output is correct
15 Correct 549 ms 112304 KB Output is correct
16 Correct 3358 ms 355832 KB Output is correct
17 Correct 2746 ms 262744 KB Output is correct
18 Correct 666 ms 98812 KB Output is correct
19 Correct 231 ms 73664 KB Output is correct
20 Correct 775 ms 104436 KB Output is correct
21 Correct 653 ms 99424 KB Output is correct
22 Correct 2017 ms 218232 KB Output is correct
23 Correct 2086 ms 223828 KB Output is correct
24 Correct 3223 ms 267120 KB Output is correct
25 Correct 3286 ms 269128 KB Output is correct
26 Correct 3122 ms 268148 KB Output is correct
27 Correct 4121 ms 361496 KB Output is correct
28 Correct 663 ms 118652 KB Output is correct
29 Correct 3011 ms 267812 KB Output is correct
30 Correct 3259 ms 267932 KB Output is correct
31 Correct 3053 ms 267448 KB Output is correct
32 Correct 908 ms 104572 KB Output is correct
33 Correct 227 ms 73704 KB Output is correct
34 Correct 487 ms 89204 KB Output is correct
35 Correct 536 ms 89940 KB Output is correct
36 Correct 661 ms 97872 KB Output is correct
37 Correct 690 ms 98000 KB Output is correct