oj.uz

Submission #1031041

# Submission time Handle Problem Language Result Execution time Memory
1031041 2024-07-22T13:49:02 Z PVSekhar Factories (JOI14_factories) C++14
0 / 100
 1546 ms 197124 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std; 
#define ll long long
// const ll MOD = 998244353;
const ll MOD = 1e9 + 7;
const ll N = 5e5 + 2;
const ll INF = 1e14 + 2;

vector<ll> dist(N);
vector<int> sz(N), is_dead(N, 0);
vector<vector<pair<int, ll>>> edges(N), cent(N);

int n;
void find_sz(int node, int parent) {
    sz[node] = 1;
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        find_sz(child.first, node);
        sz[node] += sz[child.first];
    }
}

void update(int node, int parent, int c, ll d) {
    cent[node].push_back(make_pair(c, d));
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        update(child.first, node, c, d + child.second);
    }
}

void find_cent(int node, int parent, int size) {
    for (auto child : edges[node]) {
        if (child.first == parent || is_dead[child.first]) continue;
        if (sz[child.first] * 2 > size) {
            find_cent(child.first, node, size);
            return;
        }
    }
    update(node, -1, node, 0);
    is_dead[node] = 1;
    find_sz(node, -1);
    for (auto child :edges[node]) {
        if (is_dead[child.first]) continue;
        find_cent(child.first, node, sz[child.first]);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for (int i = 0; i < N-1; i++) {
        edges[A[i]].push_back(make_pair(B[i], D[i]));
        edges[B[i]].push_back(make_pair(A[i], D[i]));
    }
    find_sz(0, -1);
    find_cent(0, -1, N);
}

long long Query(int S, int X[], int T, int Y[]) {
    ll ans = INF;
    for (int i = 0; i < T; i++) {
        for (auto p : cent[Y[i]]) {
            dist[p.first] = INT_MAX;
        }
    }
    for (int i = 0; i < S; i++) {
        for (auto p : cent[X[i]]) {
            dist[p.first] = min(dist[p.first], p.second);
        }
    }
    for (int i = 0; i < T; i++) {
        for (auto p : cent[Y[i]]) {
            ans = min(ans, dist[p.first] + p.second);
        }
    }
    return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32092 KB Output is correct
2 Correct 194 ms 40724 KB Output is correct
3 Correct 228 ms 41456 KB Output is correct
4 Incorrect 213 ms 50696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31836 KB Output is correct
2 Incorrect 1546 ms 197124 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 32092 KB Output is correct
2 Correct 194 ms 40724 KB Output is correct
3 Correct 228 ms 41456 KB Output is correct
4 Incorrect 213 ms 50696 KB Output isn't correct
5 Halted 0 ms 0 KB -