oj.uz

Submission #945218

# Submission time Handle Problem Language Result Execution time Memory
945218 2024-03-13T14:34:05 Z VMaksimoski008 Factories (JOI14_factories) C++14
100 / 100
 3874 ms 341220 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> > > 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] && 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]) 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:14:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   14 |     for(auto &[v, _] : graph[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, _] : graph[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] : graph[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] : graph[cen])
      |               ^
factories.cpp:52:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |     for(auto &[v, w] : graph[cen])
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 44380 KB Output is correct
2 Correct 184 ms 49576 KB Output is correct
3 Correct 202 ms 50028 KB Output is correct
4 Correct 208 ms 49992 KB Output is correct
5 Correct 210 ms 50516 KB Output is correct
6 Correct 143 ms 49048 KB Output is correct
7 Correct 197 ms 49820 KB Output is correct
8 Correct 200 ms 50048 KB Output is correct
9 Correct 247 ms 50572 KB Output is correct
10 Correct 141 ms 48980 KB Output is correct
11 Correct 197 ms 49968 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 44552 KB Output is correct
2 Correct 1727 ms 201652 KB Output is correct
3 Correct 2628 ms 248372 KB Output is correct
4 Correct 524 ms 97972 KB Output is correct
5 Correct 3383 ms 341220 KB Output is correct
6 Correct 2906 ms 247832 KB Output is correct
7 Correct 695 ms 87436 KB Output is correct
8 Correct 221 ms 62148 KB Output is correct
9 Correct 765 ms 92692 KB Output is correct
10 Correct 697 ms 87848 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 184 ms 49576 KB Output is correct
3 Correct 202 ms 50028 KB Output is correct
4 Correct 208 ms 49992 KB Output is correct
5 Correct 210 ms 50516 KB Output is correct
6 Correct 143 ms 49048 KB Output is correct
7 Correct 197 ms 49820 KB Output is correct
8 Correct 200 ms 50048 KB Output is correct
9 Correct 247 ms 50572 KB Output is correct
10 Correct 141 ms 48980 KB Output is correct
11 Correct 197 ms 49968 KB Output is correct
12 Correct 10 ms 44552 KB Output is correct
13 Correct 1727 ms 201652 KB Output is correct
14 Correct 2628 ms 248372 KB Output is correct
15 Correct 524 ms 97972 KB Output is correct
16 Correct 3383 ms 341220 KB Output is correct
17 Correct 2906 ms 247832 KB Output is correct
18 Correct 695 ms 87436 KB Output is correct
19 Correct 221 ms 62148 KB Output is correct
20 Correct 765 ms 92692 KB Output is correct
21 Correct 697 ms 87848 KB Output is correct
22 Correct 2088 ms 197752 KB Output is correct
23 Correct 2134 ms 202924 KB Output is correct
24 Correct 3312 ms 246736 KB Output is correct
25 Correct 3211 ms 248452 KB Output is correct
26 Correct 3108 ms 247960 KB Output is correct
27 Correct 3874 ms 341108 KB Output is correct
28 Correct 629 ms 97912 KB Output is correct
29 Correct 3145 ms 247436 KB Output is correct
30 Correct 3110 ms 247552 KB Output is correct
31 Correct 3223 ms 247260 KB Output is correct
32 Correct 912 ms 92936 KB Output is correct
33 Correct 232 ms 62228 KB Output is correct
34 Correct 460 ms 77964 KB Output is correct
35 Correct 571 ms 78992 KB Output is correct
36 Correct 685 ms 86680 KB Output is correct
37 Correct 636 ms 86872 KB Output is correct