oj.uz

Submission #1108999

# Submission time Handle Problem Language Result Execution time Memory
1108999 2024-11-05T18:39:13 Z doducanh Factories (JOI14_factories) C++14
100 / 100
 3815 ms 357932 KB 
#include <bits/stdc++.h>
//#include "factories.h"
using namespace std;
#define ll long long
#define fi first
#define se second
const ll MOD = 1e9 + 7;
const ll N = 5e5 + 2;
const ll inf = 1e14 + 2;

vector<ll> minn(N);
vector<int> sz(N), used(N, 0);
vector<vector<pair<int, ll>>> adj(N), ancestors(N);

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

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

void find_cent(int node, int parent, int size) {
    for (auto child : adj[node]) {
        if (child.first == parent || used[child.first]) continue;
        if (sz[child.first] * 2 > size) {
            find_cent(child.first, node, size);
            return;
        }
    }
    update(node, -1, node, 0);
    used[node] = 1;
    find_sz(node, -1);
    for (auto child :adj[node]) {
        if (used[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++) {
        adj[A[i]].push_back(make_pair(B[i], D[i]));
        adj[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[])
{
    for(int i=0;i<T;i++){
        for(pair<int,long long> y:ancestors[Y[i]]){
            minn[y.fi]=inf;
        }
    }
    for(int i=0;i<S;i++){
        for(pair<int,ll> y:ancestors[X[i]]){
            minn[y.fi]=min(minn[y.fi],y.se);
        }
    }
    ll ans=inf;
    for(int i=0;i<T;i++){
        for(pair<int,ll> y:ancestors[Y[i]]){
            ans=min(ans,minn[y.fi]+y.se);
        }
    }
    return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48208 KB Output is correct
2 Correct 193 ms 53296 KB Output is correct
3 Correct 204 ms 55120 KB Output is correct
4 Correct 219 ms 59420 KB Output is correct
5 Correct 243 ms 54344 KB Output is correct
6 Correct 142 ms 52808 KB Output is correct
7 Correct 207 ms 56368 KB Output is correct
8 Correct 229 ms 53840 KB Output is correct
9 Correct 223 ms 55332 KB Output is correct
10 Correct 145 ms 52808 KB Output is correct
11 Correct 203 ms 55112 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 48208 KB Output is correct
2 Correct 1538 ms 210040 KB Output is correct
3 Correct 2313 ms 283004 KB Output is correct
4 Correct 508 ms 112932 KB Output is correct
5 Correct 2670 ms 357932 KB Output is correct
6 Correct 2406 ms 293764 KB Output is correct
7 Correct 503 ms 86440 KB Output is correct
8 Correct 235 ms 63160 KB Output is correct
9 Correct 582 ms 99656 KB Output is correct
10 Correct 501 ms 92472 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48208 KB Output is correct
2 Correct 193 ms 53296 KB Output is correct
3 Correct 204 ms 55120 KB Output is correct
4 Correct 219 ms 59420 KB Output is correct
5 Correct 243 ms 54344 KB Output is correct
6 Correct 142 ms 52808 KB Output is correct
7 Correct 207 ms 56368 KB Output is correct
8 Correct 229 ms 53840 KB Output is correct
9 Correct 223 ms 55332 KB Output is correct
10 Correct 145 ms 52808 KB Output is correct
11 Correct 203 ms 55112 KB Output is correct
12 Correct 13 ms 48208 KB Output is correct
13 Correct 1538 ms 210040 KB Output is correct
14 Correct 2313 ms 283004 KB Output is correct
15 Correct 508 ms 112932 KB Output is correct
16 Correct 2670 ms 357932 KB Output is correct
17 Correct 2406 ms 293764 KB Output is correct
18 Correct 503 ms 86440 KB Output is correct
19 Correct 235 ms 63160 KB Output is correct
20 Correct 582 ms 99656 KB Output is correct
21 Correct 501 ms 92472 KB Output is correct
22 Correct 1786 ms 204656 KB Output is correct
23 Correct 1841 ms 208112 KB Output is correct
24 Correct 2962 ms 277064 KB Output is correct
25 Correct 3036 ms 290860 KB Output is correct
26 Correct 2910 ms 278688 KB Output is correct
27 Correct 3815 ms 349972 KB Output is correct
28 Correct 736 ms 102360 KB Output is correct
29 Correct 2987 ms 277708 KB Output is correct
30 Correct 3055 ms 277948 KB Output is correct
31 Correct 2654 ms 279624 KB Output is correct
32 Correct 745 ms 105716 KB Output is correct
33 Correct 253 ms 67000 KB Output is correct
34 Correct 412 ms 79840 KB Output is correct
35 Correct 452 ms 80676 KB Output is correct
36 Correct 557 ms 86088 KB Output is correct
37 Correct 566 ms 85788 KB Output is correct