oj.uz

Submission #883322

# Submission time Handle Problem Language Result Execution time Memory
883322 2023-12-05T07:15:13 Z vjudge1 Factories (JOI14_factories) C++17
0 / 100
 8000 ms 524288 KB 
//#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll INF = 1'000'000'000'000'000'000;

const int N = 500'000;
const int M = 20;

int n, q, sz[N + 10];
bool mark[N + 10];
ll mn[N + 10];
vector<pair<int, ll>> adj[N + 10];
vector<pair<int, ll>> up[N + 10];

int calcSz(int u, int par = 0) {
    sz[u] = 1;
    for (auto [v, w]: adj[u])
        if (!mark[v] && v != par)
            sz[u] += sz[v];
    return sz[u];
}

int calcCentroid(int u) {
    calcSz(u);
    int res = u;
    while (true) {
        bool ok = true;
        for (auto [v, w]: adj[res])
            if (!mark[v] && sz[v] < sz[res] && sz[v] > sz[u] / 2) {
                res = v;
                ok = false;
                break;
            }
        if (ok)
            return res;
    }
}

void calcH(int u, int root, int par = 0, ll h = 0) {
    up[u].push_back({root, h});
    for (auto [v, w]: adj[u])
        if (!mark[v] && v != par)
            calcH(v, root, u, h + w);
}

void makeGraph(int u = 1) {
    u = calcCentroid(u);
    calcH(u, u);
    mark[u] = true;
    for (auto [v, w]: adj[u])
        if (!mark[v])
            makeGraph(v);
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        A[i]++;
        B[i]++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    makeGraph();
    fill(mn + 1, mn + n + 1, INF);
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++) {
        X[i]++;
        for (auto [u, w]: up[X[i]])
            mn[u] = min(mn[u], w);
    }
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        Y[i]++;
        for (auto [u, w]: up[Y[i]])
            ans = min(ans, mn[u] + w);
    }
    for (int i = 0; i < S; i++)
        for (auto [u, w]: up[X[i]])
            mn[u] = INF;
    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 45916 KB Output is correct
2 Correct 248 ms 51872 KB Output is correct
3 Correct 921 ms 70740 KB Output is correct
4 Correct 968 ms 69532 KB Output is correct
5 Execution timed out 8055 ms 248148 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 45912 KB Output is correct
2 Correct 3214 ms 351820 KB Output is correct
3 Runtime error 4392 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 13 ms 45916 KB Output is correct
2 Correct 248 ms 51872 KB Output is correct
3 Correct 921 ms 70740 KB Output is correct
4 Correct 968 ms 69532 KB Output is correct
5 Execution timed out 8055 ms 248148 KB Time limit exceeded
6 Halted 0 ms 0 KB -