oj.uz

Submission #945216

# Submission time Handle Problem Language Result Execution time Memory
945216 2024-03-13T14:30:15 Z VMaksimoski008 Factories (JOI14_factories) C++14
100 / 100
 3984 ms 337528 KB 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
 
const int maxn = 5e5 + 5;
 
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]) 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]) get_dist(v, cen, cen, w);
 
    del[cen] = 1;
    for(auto &[v, w] : graph[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++) {
        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;
}

Compilation message

factories.cpp: In function 'int get_sub(int, int)':
factories.cpp:16:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   16 |     for(auto &[v, _] : graph[u])
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:22:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   22 |     for(auto &[v, _] : graph[u]) {
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:30:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   30 |     for(auto &[v, w] : graph[u]) {
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:38:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   38 |     for(auto &[v, d] : anc[u]) {
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:54:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |     for(auto &[v, w] : graph[cen])
      |               ^
factories.cpp:58:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |     for(auto &[v, w] : graph[cen])
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46428 KB Output is correct
2 Correct 191 ms 49580 KB Output is correct
3 Correct 227 ms 49808 KB Output is correct
4 Correct 201 ms 50000 KB Output is correct
5 Correct 208 ms 50488 KB Output is correct
6 Correct 142 ms 49036 KB Output is correct
7 Correct 200 ms 49956 KB Output is correct
8 Correct 203 ms 50004 KB Output is correct
9 Correct 215 ms 50680 KB Output is correct
10 Correct 145 ms 49032 KB Output is correct
11 Correct 196 ms 49804 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 46428 KB Output is correct
2 Correct 1712 ms 197528 KB Output is correct
3 Correct 2796 ms 244452 KB Output is correct
4 Correct 539 ms 94104 KB Output is correct
5 Correct 3342 ms 337200 KB Output is correct
6 Correct 2694 ms 244160 KB Output is correct
7 Correct 700 ms 85012 KB Output is correct
8 Correct 257 ms 59764 KB Output is correct
9 Correct 742 ms 90268 KB Output is correct
10 Correct 662 ms 85392 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 46428 KB Output is correct
2 Correct 191 ms 49580 KB Output is correct
3 Correct 227 ms 49808 KB Output is correct
4 Correct 201 ms 50000 KB Output is correct
5 Correct 208 ms 50488 KB Output is correct
6 Correct 142 ms 49036 KB Output is correct
7 Correct 200 ms 49956 KB Output is correct
8 Correct 203 ms 50004 KB Output is correct
9 Correct 215 ms 50680 KB Output is correct
10 Correct 145 ms 49032 KB Output is correct
11 Correct 196 ms 49804 KB Output is correct
12 Correct 10 ms 46428 KB Output is correct
13 Correct 1712 ms 197528 KB Output is correct
14 Correct 2796 ms 244452 KB Output is correct
15 Correct 539 ms 94104 KB Output is correct
16 Correct 3342 ms 337200 KB Output is correct
17 Correct 2694 ms 244160 KB Output is correct
18 Correct 700 ms 85012 KB Output is correct
19 Correct 257 ms 59764 KB Output is correct
20 Correct 742 ms 90268 KB Output is correct
21 Correct 662 ms 85392 KB Output is correct
22 Correct 2130 ms 193936 KB Output is correct
23 Correct 2206 ms 199020 KB Output is correct
24 Correct 3269 ms 243240 KB Output is correct
25 Correct 3254 ms 244776 KB Output is correct
26 Correct 3023 ms 244108 KB Output is correct
27 Correct 3984 ms 337528 KB Output is correct
28 Correct 661 ms 94584 KB Output is correct
29 Correct 3028 ms 243416 KB Output is correct
30 Correct 3026 ms 243432 KB Output is correct
31 Correct 3142 ms 243308 KB Output is correct
32 Correct 845 ms 90452 KB Output is correct
33 Correct 230 ms 59900 KB Output is correct
34 Correct 524 ms 75668 KB Output is correct
35 Correct 473 ms 76644 KB Output is correct
36 Correct 747 ms 84568 KB Output is correct
37 Correct 682 ms 84396 KB Output is correct