oj.uz

Submission #433417

# Submission time Handle Problem Language Result Execution time Memory
433417 2021-06-19T17:54:36 Z jovan_b Factories (JOI14_factories) C++17
100 / 100
 6948 ms 239828 KB 
#include "factories.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll INF = 1000000000000000000LL;

const int MAXN = 500000;

vector <pair <int, int>> graf[MAXN+5];
pair <int, ll> parents[MAXN+5][20];
int dokle[MAXN+5];

bool erased[MAXN+5];
int sz[MAXN+5];
ll mnd[MAXN+5];

void dfs_size(int v, int p){
    sz[v] = 1;
    for(auto c : graf[v]){
        if(erased[c.first] || c.first == p) continue;
        dfs_size(c.first, v);
        sz[v] += sz[c.first];
    }
}

int find_centroid(int v, int p, int svi){
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p && 2*sz[c.first] > svi) return find_centroid(c.first, v, svi);
    return v;
}

void dfs_depth(int v, int p, ll dst, int root){
    parents[v][++dokle[v]] = {root, dst};
    for(auto c : graf[v]) if(!erased[c.first] && c.first != p) dfs_depth(c.first, v, dst + c.second, root);
}

void decompose(){
    queue <int> q;
    q.push(1);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        dfs_size(v, 0);
        v = find_centroid(v, 0, sz[v]);
        dfs_depth(v, 0, 0, v);
        erased[v] = 1;
        for(auto c : graf[v]) if(!erased[c.first]) q.push(c.first);
    }
}

void Init(int N, int A[], int B[], int D[]) {
    for(int i=0; i<N-1; i++){
        A[i]++;
        B[i]++;
        graf[A[i]].push_back({B[i], D[i]});
        graf[B[i]].push_back({A[i], D[i]});
    }
    decompose();
    for(int i=1; i<=N; i++) reverse(parents[i]+1, parents[i]+1+dokle[i]);
    for(int i=1; i<=N; i++) mnd[i] = INF;
}

void upd(int x){
    for(int i=1; i<=dokle[x]; i++) if(mnd[parents[x][i].first] > parents[x][i].second) mnd[parents[x][i].first] = parents[x][i].second;
}

void brisi(int x){
    for(int i=1; i<=dokle[x]; i++){
        pair <int, ll> c = parents[x][i];
        if(mnd[c.first] == INF) return;
        mnd[c.first] = INF;
    }
}

ll query(int x){
    ll res = INF;
    for(int i=1; i<=dokle[x]; i++) res = min(res, parents[x][i].second + mnd[parents[x][i].first]);
    return res;
}

long long Query(int S, int X[], int T, int Y[]) {
    ll mn = INF;
    if(S < T){
        for(int i=0; i<S; i++) upd(X[i]+1);
        for(int i=0; i<T; i++) mn = min(mn, query(Y[i]+1));
        for(int i=0; i<S; i++) brisi(X[i]+1);
    }
    else{
        for(int i=0; i<T; i++) upd(Y[i]+1);
        for(int i=0; i<S; i++) mn = min(mn, query(X[i]+1));
        for(int i=0; i<T; i++) brisi(Y[i]+1);
    }
    return mn;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12492 KB Output is correct
2 Correct 324 ms 21948 KB Output is correct
3 Correct 346 ms 22000 KB Output is correct
4 Correct 302 ms 22112 KB Output is correct
5 Correct 365 ms 22212 KB Output is correct
6 Correct 327 ms 21916 KB Output is correct
7 Correct 369 ms 21924 KB Output is correct
8 Correct 293 ms 21948 KB Output is correct
9 Correct 341 ms 22208 KB Output is correct
10 Correct 290 ms 21968 KB Output is correct
11 Correct 349 ms 21920 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12236 KB Output is correct
2 Correct 3145 ms 208816 KB Output is correct
3 Correct 4896 ms 211400 KB Output is correct
4 Correct 977 ms 211200 KB Output is correct
5 Correct 6428 ms 239828 KB Output is correct
6 Correct 4921 ms 212908 KB Output is correct
7 Correct 1224 ms 60024 KB Output is correct
8 Correct 527 ms 60856 KB Output is correct
9 Correct 1535 ms 64176 KB Output is correct
10 Correct 1256 ms 61224 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12492 KB Output is correct
2 Correct 324 ms 21948 KB Output is correct
3 Correct 346 ms 22000 KB Output is correct
4 Correct 302 ms 22112 KB Output is correct
5 Correct 365 ms 22212 KB Output is correct
6 Correct 327 ms 21916 KB Output is correct
7 Correct 369 ms 21924 KB Output is correct
8 Correct 293 ms 21948 KB Output is correct
9 Correct 341 ms 22208 KB Output is correct
10 Correct 290 ms 21968 KB Output is correct
11 Correct 349 ms 21920 KB Output is correct
12 Correct 9 ms 12236 KB Output is correct
13 Correct 3145 ms 208816 KB Output is correct
14 Correct 4896 ms 211400 KB Output is correct
15 Correct 977 ms 211200 KB Output is correct
16 Correct 6428 ms 239828 KB Output is correct
17 Correct 4921 ms 212908 KB Output is correct
18 Correct 1224 ms 60024 KB Output is correct
19 Correct 527 ms 60856 KB Output is correct
20 Correct 1535 ms 64176 KB Output is correct
21 Correct 1256 ms 61224 KB Output is correct
22 Correct 3695 ms 210376 KB Output is correct
23 Correct 3634 ms 212728 KB Output is correct
24 Correct 5524 ms 213012 KB Output is correct
25 Correct 5482 ms 216592 KB Output is correct
26 Correct 5537 ms 213324 KB Output is correct
27 Correct 6948 ms 236664 KB Output is correct
28 Correct 1296 ms 215168 KB Output is correct
29 Correct 5317 ms 213064 KB Output is correct
30 Correct 5431 ms 212384 KB Output is correct
31 Correct 5448 ms 213252 KB Output is correct
32 Correct 1421 ms 66196 KB Output is correct
33 Correct 681 ms 62268 KB Output is correct
34 Correct 989 ms 58868 KB Output is correct
35 Correct 1010 ms 59080 KB Output is correct
36 Correct 1286 ms 59460 KB Output is correct
37 Correct 1229 ms 59624 KB Output is correct