oj.uz

Submission #908152

# Submission time Handle Problem Language Result Execution time Memory
908152 2024-01-16T08:46:33 Z typ_ik Factories (JOI14_factories) C++17
0 / 100
 2211 ms 77468 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;

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];
map <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 = 1; 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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 60252 KB Output is correct
2 Correct 1220 ms 75788 KB Output is correct
3 Correct 1780 ms 76680 KB Output is correct
4 Correct 1834 ms 76632 KB Output is correct
5 Correct 2211 ms 77468 KB Output is correct
6 Incorrect 350 ms 74260 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 59992 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 60252 KB Output is correct
2 Correct 1220 ms 75788 KB Output is correct
3 Correct 1780 ms 76680 KB Output is correct
4 Correct 1834 ms 76632 KB Output is correct
5 Correct 2211 ms 77468 KB Output is correct
6 Incorrect 350 ms 74260 KB Output isn't correct
7 Halted 0 ms 0 KB -