oj.uz

Submission #116545

# Submission time Handle Problem Language Result Execution time Memory
116545 2019-06-12T22:14:34 Z YazanZk Factories (JOI14_factories) C++14
100 / 100
 7386 ms 233492 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

const int N = 5 * 1e5 + 1 ;
const ll inf = 1e18 ;

vector < pair < int, int > > G[N];
int sub[N], p[N] , par[N];
bitset < N > blocked;

void get_size(int u, int pa) {
    p[u] = pa ;
    sub[u] = 1 ;
    for(auto e : G[u]) {
        int v = e.first ;
        if(blocked[v] || v == pa) continue ;
        get_size(v, u);
        sub[u] += sub[v];
    }
}

vector < ll > dis[N];

void solve(int u , int p , ll d){
     for(auto e : G[u]){
          int v = e.first , w = e.second ;
          if(blocked[v] || v == p) continue ;
          dis[v].push_back(d + w);
          solve(v , u , d + w);
     }
}

int get_centroid(int src) {

    get_size(src, src);

    int centroid = src, best = sub[src] ;
    queue < int > Q ;
    Q.emplace(src);

    while(!Q.empty()) {
        int u = Q.front();
        Q.pop();

        int size = sub[src] - sub[u];
        for(auto e : G[u]) {
            int v = e.first;
            if(blocked[v] || v == p[u])
                continue ;
            Q.emplace(v);
            size = max(size, sub[v]);
        }

        if(best > size) {
            best = size;
            centroid = u ;
        }
    }

    blocked[centroid] = true;

    solve(centroid , centroid , 0);

    for(auto e : G[centroid]) {
        int v = e.first ;
        if(blocked[v]) continue ;
        int child = get_centroid(v);
        par[child] = centroid ;
    }

    return centroid ;
}

ll ans[N];
int vis[N];
int t = 1 ;

inline void update(int &u) {
    int v = u ;
    int i = dis[u].size() - 1;
    while(true) {
        if(vis[v] != t)
            vis[v] = t , ans[v] = inf ;
        ans[v] = min(ans[v], dis[u][i]);
        if(v == par[v]) break ;
        v = par[v];
        i--;
    }
}

inline ll query(int &u) {
    int v = u;
    ll ret = inf ;
    int i = dis[u].size() - 1 ;
    while(true) {
        if(vis[v] != t)
            vis[v] = t , ans[v] = inf ;
        ret = min(ret, ans[v] + dis[u][i]);
        if(v == par[v]) break ;
        v = par[v];
        i-- ;
    }
    return ret;
}


ll Query(int S, int X[N], int T, int Y[N]) {

    t++ ;

    for(int i = 0 ; i < T ; i++) {
        update(Y[i]);
    }

    ll ret = inf ;
    for(int i = 0 ; i < S ; i++) {
        ret = min(ret,  query(X[i]));
    }

    return ret;
}

void Init(int n , int A[N], int B[N], int D[N]) {


    for(int i = 0 ; i < n - 1 ; i++) {
        int u = A[i], v = B[i], w = D[i];
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    int root = get_centroid(0);
    par[root] = root;

    for(int i = 0 ; i < n ; i++) dis[i].push_back(0);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24440 KB Output is correct
2 Correct 333 ms 34084 KB Output is correct
3 Correct 381 ms 33948 KB Output is correct
4 Correct 365 ms 33784 KB Output is correct
5 Correct 431 ms 34060 KB Output is correct
6 Correct 264 ms 33272 KB Output is correct
7 Correct 369 ms 33768 KB Output is correct
8 Correct 377 ms 34040 KB Output is correct
9 Correct 389 ms 34180 KB Output is correct
10 Correct 265 ms 33272 KB Output is correct
11 Correct 371 ms 33784 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24064 KB Output is correct
2 Correct 3521 ms 137208 KB Output is correct
3 Correct 5440 ms 181812 KB Output is correct
4 Correct 1241 ms 83724 KB Output is correct
5 Correct 6658 ms 233492 KB Output is correct
6 Correct 5598 ms 182480 KB Output is correct
7 Correct 1331 ms 56624 KB Output is correct
8 Correct 482 ms 45596 KB Output is correct
9 Correct 1478 ms 69844 KB Output is correct
10 Correct 1225 ms 57592 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24440 KB Output is correct
2 Correct 333 ms 34084 KB Output is correct
3 Correct 381 ms 33948 KB Output is correct
4 Correct 365 ms 33784 KB Output is correct
5 Correct 431 ms 34060 KB Output is correct
6 Correct 264 ms 33272 KB Output is correct
7 Correct 369 ms 33768 KB Output is correct
8 Correct 377 ms 34040 KB Output is correct
9 Correct 389 ms 34180 KB Output is correct
10 Correct 265 ms 33272 KB Output is correct
11 Correct 371 ms 33784 KB Output is correct
12 Correct 24 ms 24064 KB Output is correct
13 Correct 3521 ms 137208 KB Output is correct
14 Correct 5440 ms 181812 KB Output is correct
15 Correct 1241 ms 83724 KB Output is correct
16 Correct 6658 ms 233492 KB Output is correct
17 Correct 5598 ms 182480 KB Output is correct
18 Correct 1331 ms 56624 KB Output is correct
19 Correct 482 ms 45596 KB Output is correct
20 Correct 1478 ms 69844 KB Output is correct
21 Correct 1225 ms 57592 KB Output is correct
22 Correct 3690 ms 138368 KB Output is correct
23 Correct 4021 ms 141076 KB Output is correct
24 Correct 5944 ms 182992 KB Output is correct
25 Correct 5967 ms 186716 KB Output is correct
26 Correct 5863 ms 183708 KB Output is correct
27 Correct 7386 ms 230372 KB Output is correct
28 Correct 1572 ms 87768 KB Output is correct
29 Correct 5886 ms 182940 KB Output is correct
30 Correct 5788 ms 182420 KB Output is correct
31 Correct 5950 ms 183044 KB Output is correct
32 Correct 1659 ms 83544 KB Output is correct
33 Correct 439 ms 59164 KB Output is correct
34 Correct 945 ms 65600 KB Output is correct
35 Correct 910 ms 65932 KB Output is correct
36 Correct 1411 ms 67628 KB Output is correct
37 Correct 1334 ms 67764 KB Output is correct