oj.uz

Submission #908170

# Submission time Handle Problem Language Result Execution time Memory
908170 2024-01-16T09:02:27 Z typ_ik Factories (JOI14_factories) C++17
15 / 100
 3217 ms 524288 KB 
#include <bits/stdc++.h>
#include "factories.h"

#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

const int N = 5e5 + 128;
const ll INF = 1e15 + 128;
vector < pair<int, int> > g[N];
int n, q;
bool was[N];
int h[N];
gp_hash_table <int, ll> d[N];
ll res[N];

void dfs(int v, int p = -1) {
    h[v] = 1;   

    for (auto& [to, len] : g[v])
        if (to != p && !was[to])
            dfs(to, v), h[v] += h[to];
}

void calc(int v, int cent, ll val, int p) {
    d[cent][v] = val;

    for (auto& [to, len] : g[v])
        if (to != p && !was[to])
            calc(to, cent, val+len, v);
}

int find_centroid(int v, int p, int sz) { 
    for (auto& [to, len] : g[v])
        if (to != p && h[to] > sz / 2 && !was[to])
            return find_centroid(to, v, sz);
    return v;
}

int p[N];

void decompose(int v, int pr = -1) { 
    dfs(v); 

    int c = find_centroid(v, -1, h[v]);  

    calc(c, c, 0, -1);

    p[c] = pr;
    was[c] = true;

    for (auto& [to, len] : g[c])
        if (!was[to])
            decompose(to, c);
}

void update(int v) {
    int c = v;
    while (c != -1) 
        res[c] = min(res[c], d[c][v]), c = p[c];
}

void reset(int v) {
    int c = v;
    while (c != -1) 
        res[c] = INF, c = p[c]; 
}

ll get(int v) {
    ll ans = INF;
    int c = v;
    while (c != -1)
        ans = min(ans, d[c][v]+res[c]), c = p[c];
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i + 1 < n; i++) {
        int u = A[i], v = B[i], w = D[i];
        g[u].push_back(make_pair(v, w));
        g[v].push_back(make_pair(u, w));
    }
    for (int i = 0; i <= n; i++)
        res[i] = INF, p[i] = -1;
    decompose(1);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        update(X[i]);
    ll tot = INF;
    for (int i = 0; i < T; i++)
        tot = min(tot, get(Y[i]));
    for (int i = 0; i < S; i++)
        reset(X[i]);
    return tot;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 188424 KB Output is correct
2 Correct 405 ms 194776 KB Output is correct
3 Correct 482 ms 195828 KB Output is correct
4 Correct 454 ms 195732 KB Output is correct
5 Correct 478 ms 196940 KB Output is correct
6 Correct 289 ms 193252 KB Output is correct
7 Correct 445 ms 195720 KB Output is correct
8 Correct 472 ms 195960 KB Output is correct
9 Correct 476 ms 196708 KB Output is correct
10 Correct 261 ms 193108 KB Output is correct
11 Correct 439 ms 195628 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 188372 KB Output is correct
2 Correct 3217 ms 522412 KB Output is correct
3 Runtime error 2410 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 109 ms 188424 KB Output is correct
2 Correct 405 ms 194776 KB Output is correct
3 Correct 482 ms 195828 KB Output is correct
4 Correct 454 ms 195732 KB Output is correct
5 Correct 478 ms 196940 KB Output is correct
6 Correct 289 ms 193252 KB Output is correct
7 Correct 445 ms 195720 KB Output is correct
8 Correct 472 ms 195960 KB Output is correct
9 Correct 476 ms 196708 KB Output is correct
10 Correct 261 ms 193108 KB Output is correct
11 Correct 439 ms 195628 KB Output is correct
12 Correct 104 ms 188372 KB Output is correct
13 Correct 3217 ms 522412 KB Output is correct
14 Runtime error 2410 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -