oj.uz

Submission #872064

# Submission time Handle Problem Language Result Execution time Memory
872064 2023-11-12T08:46:54 Z vjudge1 Factories (JOI14_factories) C++17
0 / 100
 14 ms 33116 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[]) {
    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]) {
        a[v] = min(a[v], a[u] + w);
        b[v] = min(b[v], b[u] + w);

        if (u != p)
            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 Incorrect 14 ms 33112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

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

Subtask #3
0 / 67.0

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