oj.uz

Submission #945221

# Submission time Handle Problem Language Result Execution time Memory
945221 2024-03-13T14:38:35 Z VMaksimoski008 Factories (JOI14_factories) C++14
100 / 100
 3907 ms 341332 KB 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
using ll = long long;
 
const int maxn = 5e5 + 5;
 
ll n, del[maxn], sub[maxn], dist[maxn];
vector<vector<pair<ll, ll> > > G(maxn), anc(maxn);
 
int get_sub(int u, int p) {
    sub[u] = 1;
    for(auto &[v, _] : G[u])
        if(v != p && !del[v]) sub[u] += get_sub(v, u);
    return sub[u];
}
 
int get_cen(int u, int p, int sz) {
    for(auto &[v, _] : G[u])
        if(v != p && !del[v] && 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] : G[u])
        if(v != p && !del[v]) 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] : G[cen])
        if(!del[v]) get_dist(v, cen, cen, w);
 
    del[cen] = 1;
    for(auto &[v, w] : G[cen])
        if(!del[v]) build(v);
}
 
void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i=0; i<n-1; i++) {
        G[A[i]].push_back({ B[i], D[i] });
        G[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;
}

Compilation message

factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto &[v, _] : G[u])
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for(auto &[v, _] : G[u])
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:26:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   26 |     for(auto &[v, w] : G[u])
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:32:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   32 |     for(auto &[v, d] : anc[u]) {
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:41:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |     for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:48:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   48 |     for(auto &[v, w] : G[cen])
      |               ^
factories.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto &[v, w] : G[cen])
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 44380 KB Output is correct
2 Correct 186 ms 49548 KB Output is correct
3 Correct 215 ms 50060 KB Output is correct
4 Correct 209 ms 50016 KB Output is correct
5 Correct 208 ms 50316 KB Output is correct
6 Correct 143 ms 49024 KB Output is correct
7 Correct 220 ms 49964 KB Output is correct
8 Correct 197 ms 50064 KB Output is correct
9 Correct 207 ms 50516 KB Output is correct
10 Correct 144 ms 49048 KB Output is correct
11 Correct 195 ms 49968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 44380 KB Output is correct
2 Correct 1786 ms 201408 KB Output is correct
3 Correct 2685 ms 248332 KB Output is correct
4 Correct 534 ms 97972 KB Output is correct
5 Correct 3496 ms 341084 KB Output is correct
6 Correct 2835 ms 247868 KB Output is correct
7 Correct 741 ms 87432 KB Output is correct
8 Correct 249 ms 62200 KB Output is correct
9 Correct 831 ms 92696 KB Output is correct
10 Correct 713 ms 87692 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 44380 KB Output is correct
2 Correct 186 ms 49548 KB Output is correct
3 Correct 215 ms 50060 KB Output is correct
4 Correct 209 ms 50016 KB Output is correct
5 Correct 208 ms 50316 KB Output is correct
6 Correct 143 ms 49024 KB Output is correct
7 Correct 220 ms 49964 KB Output is correct
8 Correct 197 ms 50064 KB Output is correct
9 Correct 207 ms 50516 KB Output is correct
10 Correct 144 ms 49048 KB Output is correct
11 Correct 195 ms 49968 KB Output is correct
12 Correct 10 ms 44380 KB Output is correct
13 Correct 1786 ms 201408 KB Output is correct
14 Correct 2685 ms 248332 KB Output is correct
15 Correct 534 ms 97972 KB Output is correct
16 Correct 3496 ms 341084 KB Output is correct
17 Correct 2835 ms 247868 KB Output is correct
18 Correct 741 ms 87432 KB Output is correct
19 Correct 249 ms 62200 KB Output is correct
20 Correct 831 ms 92696 KB Output is correct
21 Correct 713 ms 87692 KB Output is correct
22 Correct 2188 ms 197728 KB Output is correct
23 Correct 2156 ms 202988 KB Output is correct
24 Correct 3343 ms 246756 KB Output is correct
25 Correct 3402 ms 248252 KB Output is correct
26 Correct 3128 ms 247940 KB Output is correct
27 Correct 3907 ms 341332 KB Output is correct
28 Correct 649 ms 98032 KB Output is correct
29 Correct 3229 ms 247324 KB Output is correct
30 Correct 3156 ms 247684 KB Output is correct
31 Correct 3231 ms 247252 KB Output is correct
32 Correct 843 ms 92824 KB Output is correct
33 Correct 225 ms 62216 KB Output is correct
34 Correct 451 ms 77964 KB Output is correct
35 Correct 583 ms 79064 KB Output is correct
36 Correct 726 ms 86792 KB Output is correct
37 Correct 777 ms 86848 KB Output is correct