oj.uz

Submission #908166

# Submission time Handle Problem Language Result Execution time Memory
908166 2024-01-16T08:57:50 Z typ_ik Factories (JOI14_factories) C++17
15 / 100
 8000 ms 429844 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 = 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 29 ms 60248 KB Output is correct
2 Correct 1216 ms 71204 KB Output is correct
3 Correct 1793 ms 72116 KB Output is correct
4 Correct 1817 ms 72040 KB Output is correct
5 Correct 2210 ms 72884 KB Output is correct
6 Correct 340 ms 69768 KB Output is correct
7 Correct 1832 ms 76636 KB Output is correct
8 Correct 1940 ms 76744 KB Output is correct
9 Correct 2333 ms 77468 KB Output is correct
10 Correct 349 ms 74368 KB Output is correct
11 Correct 1835 ms 76636 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 59996 KB Output is correct
2 Execution timed out 8066 ms 429844 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 60248 KB Output is correct
2 Correct 1216 ms 71204 KB Output is correct
3 Correct 1793 ms 72116 KB Output is correct
4 Correct 1817 ms 72040 KB Output is correct
5 Correct 2210 ms 72884 KB Output is correct
6 Correct 340 ms 69768 KB Output is correct
7 Correct 1832 ms 76636 KB Output is correct
8 Correct 1940 ms 76744 KB Output is correct
9 Correct 2333 ms 77468 KB Output is correct
10 Correct 349 ms 74368 KB Output is correct
11 Correct 1835 ms 76636 KB Output is correct
12 Correct 17 ms 59996 KB Output is correct
13 Execution timed out 8066 ms 429844 KB Time limit exceeded
14 Halted 0 ms 0 KB -