oj.uz

Submission #872071

# Submission time Handle Problem Language Result Execution time Memory
872071 2023-11-12T08:59:10 Z vjudge1 Factories (JOI14_factories) C++17
0 / 100
 27 ms 50400 KB 
#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

typedef pair<int, long long> pii;

const int N = 500'000 + 7;
vector<pii> adj[N];
int n;
long long a[N], b[N];
bool x[N], y[N];

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

void dfs(int v, int p) {
    if (x[v])
        a[v] = 0;
    if (y[v])
        b[v] = 0;

    for (auto [u, w] : adj[v])
        if (u != p) {
            a[v] = min(a[v], a[u] + w);
            b[v] = min(b[v], b[u] + w);

            dfs(u, v);
        }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < n; i++)
        x[i] = y[i] = false, a[i] = b[i] = 1e18;
    for (int i = 0; i < S; i++)
        x[X[i]] = true;
    for (int i = 0; i < T; i++)
        y[Y[i]] = true;

    dfs(0, 0);
    long long res = 1e18;
    for (int i = 0; i < n; i++)
        res = min(res, a[i] + b[i]);
    return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 50400 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 50304 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Runtime error 27 ms 50400 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -