oj.uz

Submission #81592

# Submission time Handle Problem Language Result Execution time Memory
81592 2018-10-25T13:14:23 Z chelly Factories (JOI14_factories) C++17
100 / 100
 5608 ms 382268 KB 
#include"factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int MAXN = 500001;
int level[MAXN], sz[MAXN], par[MAXN][20];
ll dis[MAXN][20], dis1[MAXN];
bool done[MAXN], contains[MAXN];
int N, Q;
vector<pii> adj[MAXN];
queue<int> s;
void dfs (int u, int p){
    sz[u] = 1;
    for (pii e: adj[u]){
        if (e.first==p||done[e.first]) continue;
        dfs (e.first, u);
        sz[u]+=sz[e.first];
    }
}
void dfs1(int u, int p, int l, ll d, int pa){
    dis[u][l] = d;
    par[u][l] = pa;
    for (pii e: adj[u]){
        if (e.first==p||done[e.first]) continue;
        dfs1(e.first, u, l, d+e.second, pa);
    }
}
int centroid (int u, int p, int S){
    for (pii e: adj[u]){
        if (sz[e.first]*2>S&&e.first!=p&&!done[e.first]) return centroid (e.first, u, S);
    }
    return u;
}
void build (int u, int p, int l){
    dfs (u, -1);
    u = centroid(u, -1, sz[u]);
    level[u] = l;
    dfs1(u, -1, l, 0, u);
    done[u] = true;
    for (pii e: adj[u]){
        if (!done[e.first]&&e.first!=p) build(e.first, u, l+1);
    }
}

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]));
    }
    memset (dis, -1, sizeof dis);
    memset (par, -1, sizeof par);
    memset (dis1, -1, sizeof dis1);
    build(0, -1, 1);
}

ll Query(int S, int X[], int T, int Y[]){
     while(!s.empty()){
        dis1[s.front()]=-1;
        contains[s.front()] = false;
        s.pop();
    }
    ll best = -1;
    for (int i = 0; i<S; i++){
        int A = X[i];
        int l = level[A];
        while (l){
            if (dis1[par[A][l]]==-1) dis1[par[A][l]] = dis[A][l];
            else dis1[par[A][l]]=min(dis1[par[A][l]], dis[A][l]);
            if (!contains[par[A][l]]){
                contains[par[A][l]] = true;
                s.push(par[A][l]);
            }
            l--;
        }
    }
    for (int i = 0; i<T; i++){
        int B = Y[i];
        int l = level[B];
        while (l){
            if(best==-1&&dis1[par[B][l]]!=-1)best = dis1[par[B][l]]+dis[B][l];
            else if (dis1[par[B][l]]!=-1) best = min(best, dis1[par[B][l]]+dis[B][l]);
            l--;
        }
    }
    return best;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 133884 KB Output is correct
2 Correct 533 ms 151488 KB Output is correct
3 Correct 570 ms 161244 KB Output is correct
4 Correct 526 ms 170460 KB Output is correct
5 Correct 563 ms 180336 KB Output is correct
6 Correct 411 ms 189564 KB Output is correct
7 Correct 538 ms 199028 KB Output is correct
8 Correct 540 ms 199920 KB Output is correct
9 Correct 560 ms 200164 KB Output is correct
10 Correct 408 ms 200164 KB Output is correct
11 Correct 561 ms 200164 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 200164 KB Output is correct
2 Correct 2495 ms 227692 KB Output is correct
3 Correct 3641 ms 231388 KB Output is correct
4 Correct 1207 ms 231388 KB Output is correct
5 Correct 4720 ms 253424 KB Output is correct
6 Correct 3729 ms 253424 KB Output is correct
7 Correct 1288 ms 253424 KB Output is correct
8 Correct 783 ms 253424 KB Output is correct
9 Correct 1398 ms 253424 KB Output is correct
10 Correct 1235 ms 253424 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 133884 KB Output is correct
2 Correct 533 ms 151488 KB Output is correct
3 Correct 570 ms 161244 KB Output is correct
4 Correct 526 ms 170460 KB Output is correct
5 Correct 563 ms 180336 KB Output is correct
6 Correct 411 ms 189564 KB Output is correct
7 Correct 538 ms 199028 KB Output is correct
8 Correct 540 ms 199920 KB Output is correct
9 Correct 560 ms 200164 KB Output is correct
10 Correct 408 ms 200164 KB Output is correct
11 Correct 561 ms 200164 KB Output is correct
12 Correct 102 ms 200164 KB Output is correct
13 Correct 2495 ms 227692 KB Output is correct
14 Correct 3641 ms 231388 KB Output is correct
15 Correct 1207 ms 231388 KB Output is correct
16 Correct 4720 ms 253424 KB Output is correct
17 Correct 3729 ms 253424 KB Output is correct
18 Correct 1288 ms 253424 KB Output is correct
19 Correct 783 ms 253424 KB Output is correct
20 Correct 1398 ms 253424 KB Output is correct
21 Correct 1235 ms 253424 KB Output is correct
22 Correct 2916 ms 253424 KB Output is correct
23 Correct 3047 ms 253424 KB Output is correct
24 Correct 4469 ms 253424 KB Output is correct
25 Correct 4614 ms 253424 KB Output is correct
26 Correct 4524 ms 253424 KB Output is correct
27 Correct 5608 ms 253748 KB Output is correct
28 Correct 1698 ms 259780 KB Output is correct
29 Correct 4347 ms 282424 KB Output is correct
30 Correct 4396 ms 304524 KB Output is correct
31 Correct 4321 ms 328612 KB Output is correct
32 Correct 1433 ms 328612 KB Output is correct
33 Correct 807 ms 333760 KB Output is correct
34 Correct 1082 ms 343376 KB Output is correct
35 Correct 1026 ms 356208 KB Output is correct
36 Correct 1255 ms 369328 KB Output is correct
37 Correct 1375 ms 382268 KB Output is correct