oj.uz

Submission #445182

# Submission time Handle Problem Language Result Execution time Memory
445182 2021-07-16T18:47:53 Z JovanB Factories (JOI14_factories) C++17
100 / 100
 5762 ms 261312 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 14 ms 12620 KB Output is correct
2 Correct 308 ms 31372 KB Output is correct
3 Correct 349 ms 31828 KB Output is correct
4 Correct 291 ms 31452 KB Output is correct
5 Correct 345 ms 31856 KB Output is correct
6 Correct 255 ms 31400 KB Output is correct
7 Correct 344 ms 31480 KB Output is correct
8 Correct 294 ms 31432 KB Output is correct
9 Correct 345 ms 31700 KB Output is correct
10 Correct 264 ms 31492 KB Output is correct
11 Correct 343 ms 31388 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12364 KB Output is correct
2 Correct 2581 ms 227444 KB Output is correct
3 Correct 4078 ms 229272 KB Output is correct
4 Correct 919 ms 229444 KB Output is correct
5 Correct 5431 ms 258576 KB Output is correct
6 Correct 4107 ms 231364 KB Output is correct
7 Correct 1020 ms 73760 KB Output is correct
8 Correct 493 ms 74768 KB Output is correct
9 Correct 1151 ms 78176 KB Output is correct
10 Correct 1113 ms 75284 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 12620 KB Output is correct
2 Correct 308 ms 31372 KB Output is correct
3 Correct 349 ms 31828 KB Output is correct
4 Correct 291 ms 31452 KB Output is correct
5 Correct 345 ms 31856 KB Output is correct
6 Correct 255 ms 31400 KB Output is correct
7 Correct 344 ms 31480 KB Output is correct
8 Correct 294 ms 31432 KB Output is correct
9 Correct 345 ms 31700 KB Output is correct
10 Correct 264 ms 31492 KB Output is correct
11 Correct 343 ms 31388 KB Output is correct
12 Correct 10 ms 12364 KB Output is correct
13 Correct 2581 ms 227444 KB Output is correct
14 Correct 4078 ms 229272 KB Output is correct
15 Correct 919 ms 229444 KB Output is correct
16 Correct 5431 ms 258576 KB Output is correct
17 Correct 4107 ms 231364 KB Output is correct
18 Correct 1020 ms 73760 KB Output is correct
19 Correct 493 ms 74768 KB Output is correct
20 Correct 1151 ms 78176 KB Output is correct
21 Correct 1113 ms 75284 KB Output is correct
22 Correct 2983 ms 234672 KB Output is correct
23 Correct 2973 ms 237504 KB Output is correct
24 Correct 4354 ms 237412 KB Output is correct
25 Correct 4560 ms 241308 KB Output is correct
26 Correct 4569 ms 237580 KB Output is correct
27 Correct 5762 ms 261312 KB Output is correct
28 Correct 1113 ms 239876 KB Output is correct
29 Correct 4367 ms 237248 KB Output is correct
30 Correct 4405 ms 236568 KB Output is correct
31 Correct 4400 ms 237376 KB Output is correct
32 Correct 1107 ms 79180 KB Output is correct
33 Correct 520 ms 75240 KB Output is correct
34 Correct 817 ms 71568 KB Output is correct
35 Correct 810 ms 71608 KB Output is correct
36 Correct 961 ms 72120 KB Output is correct
37 Correct 959 ms 72268 KB Output is correct