oj.uz

Submission #945220

# Submission time Handle Problem Language Result Execution time Memory
945220 2024-03-13T14:37:53 Z VMaksimoski008 Factories (JOI14_factories) C++14
15 / 100
 6807 ms 524288 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) {
    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:13:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   13 |     for(auto &[v, _] : G[u])
      |               ^
factories.cpp: In function 'int get_cen(int, int, int)':
factories.cpp:19:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   19 |     for(auto &[v, _] : G[u])
      |               ^
factories.cpp: In function 'void get_dist(int, int, int, ll)':
factories.cpp:25:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |     for(auto &[v, w] : G[u])
      |               ^
factories.cpp: In function 'void update(int, int)':
factories.cpp:31:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |     for(auto &[v, d] : anc[u]) {
      |               ^
factories.cpp: In function 'll query(int)':
factories.cpp:40:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |     for(auto &[v, d] : anc[u]) ans = min(ans, d + dist[v]);
      |               ^
factories.cpp: In function 'void build(int)':
factories.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for(auto &[v, w] : G[cen])
      |               ^
factories.cpp:51:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |     for(auto &[v, w] : G[cen])
      |               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42324 KB Output is correct
2 Correct 197 ms 47652 KB Output is correct
3 Correct 370 ms 53076 KB Output is correct
4 Correct 372 ms 53136 KB Output is correct
5 Correct 1302 ms 72900 KB Output is correct
6 Correct 143 ms 47188 KB Output is correct
7 Correct 338 ms 52048 KB Output is correct
8 Correct 363 ms 53244 KB Output is correct
9 Correct 1343 ms 72904 KB Output is correct
10 Correct 144 ms 46924 KB Output is correct
11 Correct 339 ms 52116 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 42328 KB Output is correct
2 Correct 2013 ms 216952 KB Output is correct
3 Runtime error 6807 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 42324 KB Output is correct
2 Correct 197 ms 47652 KB Output is correct
3 Correct 370 ms 53076 KB Output is correct
4 Correct 372 ms 53136 KB Output is correct
5 Correct 1302 ms 72900 KB Output is correct
6 Correct 143 ms 47188 KB Output is correct
7 Correct 338 ms 52048 KB Output is correct
8 Correct 363 ms 53244 KB Output is correct
9 Correct 1343 ms 72904 KB Output is correct
10 Correct 144 ms 46924 KB Output is correct
11 Correct 339 ms 52116 KB Output is correct
12 Correct 11 ms 42328 KB Output is correct
13 Correct 2013 ms 216952 KB Output is correct
14 Runtime error 6807 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -