oj.uz

Submission #908168

# Submission time Handle Problem Language Result Execution time Memory
908168 2024-01-16T08:59:23 Z typ_ik Factories (JOI14_factories) C++17
15 / 100
 3202 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 p[N], 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;
}

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));
    }
    decompose(1);
    for (int i = 0; i <= n; i++)
        res[i] = INF;
}

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 101 ms 188500 KB Output is correct
2 Correct 391 ms 194524 KB Output is correct
3 Correct 428 ms 195848 KB Output is correct
4 Correct 447 ms 195748 KB Output is correct
5 Correct 476 ms 196940 KB Output is correct
6 Correct 264 ms 193260 KB Output is correct
7 Correct 442 ms 195920 KB Output is correct
8 Correct 440 ms 195980 KB Output is correct
9 Correct 482 ms 196940 KB Output is correct
10 Correct 254 ms 193248 KB Output is correct
11 Correct 449 ms 195548 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 188404 KB Output is correct
2 Correct 3202 ms 522304 KB Output is correct
3 Runtime error 2528 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 101 ms 188500 KB Output is correct
2 Correct 391 ms 194524 KB Output is correct
3 Correct 428 ms 195848 KB Output is correct
4 Correct 447 ms 195748 KB Output is correct
5 Correct 476 ms 196940 KB Output is correct
6 Correct 264 ms 193260 KB Output is correct
7 Correct 442 ms 195920 KB Output is correct
8 Correct 440 ms 195980 KB Output is correct
9 Correct 482 ms 196940 KB Output is correct
10 Correct 254 ms 193248 KB Output is correct
11 Correct 449 ms 195548 KB Output is correct
12 Correct 97 ms 188404 KB Output is correct
13 Correct 3202 ms 522304 KB Output is correct
14 Runtime error 2528 ms 524288 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -