oj.uz

Submission #171120

# Submission time Handle Problem Language Result Execution time Memory
171120 2019-12-27T13:13:16 Z dantoh000 Factories (JOI14_factories) C++14
100 / 100
 5933 ms 169792 KB 
#include <bits/stdc++.h>
#include "factories.h"
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int SZ = 500005;
const ll INF = 1000000000000000000;
int par[SZ], lvl[SZ], sub[SZ];
ll dist[SZ][20], ans[SZ];
vector<ii> adjlist[SZ];
stack<int> st;
int dfs1(int u, int p, int l){
    sub[u] = 1;
    for (auto v : adjlist[u]){
        if (lvl[v.fi] != -1 || v.fi == p) continue;
        sub[u] += dfs1(v.fi,u,l);
    }
    return sub[u];
}
int dfs2(int u, int p, int n){
    for (auto v : adjlist[u]){
        if (lvl[v.fi] != -1 || v.fi == p) continue;
        if (sub[v.fi] > n/2) return dfs2(v.fi,u,n);
    }
    return u;
}
void dfs3(int u, int p, int l, ll d){
    //printf("dist %d %d = %lld\n",u,l,d);
    dist[u][l] = d;
    for (auto v : adjlist[u]){
        if (lvl[v.fi] != -1 || v.fi == p) continue;
        dfs3(v.fi,u,l,d+v.se);
    }
}
void build(int u, int p, int l){
    int n = dfs1(u,p,l);
    int cent = dfs2(u,p,n);
    dfs3(cent,-1,l,0);
    if (p == -1) p = cent;
    //printf("built %d %d %d\n",cent,p,l);
    par[cent] = p;
    lvl[cent] = l;
    for (auto v : adjlist[cent]){
        if (lvl[v.fi] != -1) continue;
        build(v.fi,cent,l+1);
    }
}
void update(int x){
    int l = lvl[x];
    int y = x;
    while (l != -1){
        //printf("updating %d %d: %lld\n",x,y,dist[x][l]);
        ans[y] = min(ans[y],dist[x][l]);
        st.push(y);
        y = par[y];
        l--;
    }
}
ll query(int x){
    ll res = INF;
    int l = lvl[x];
    int y = x;
    while (l != -1){
        //printf("at %d (level %d), nearest is %d\n",y,l,ans[y]);
        res = min(res,ans[y]+dist[x][l]);
        y = par[y];
        l--;
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]){
    memset(ans,127,sizeof(ans));
    memset(lvl,-1,sizeof(lvl));
    for (int i = 0; i < N-1; i++){
        adjlist[A[i]].push_back(ii(B[i],D[i]));
        adjlist[B[i]].push_back(ii(A[i],D[i]));
    }
    build(0,-1,0);
}
ll Query(int S, int X[], int T, int Y[]){
    for (int i = 0; i < S; i++){
        update(X[i]);
    }
    ll res = INF;
    for (int i = 0; i < T; i++){
        res = min(res,query(Y[i]));
    }
    while (st.size()){
        ans[st.top()] = INF;
        st.pop();
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18552 KB Output is correct
2 Correct 386 ms 36672 KB Output is correct
3 Correct 422 ms 36600 KB Output is correct
4 Correct 425 ms 36732 KB Output is correct
5 Correct 446 ms 37104 KB Output is correct
6 Correct 311 ms 36628 KB Output is correct
7 Correct 538 ms 36752 KB Output is correct
8 Correct 426 ms 36748 KB Output is correct
9 Correct 451 ms 36848 KB Output is correct
10 Correct 312 ms 36564 KB Output is correct
11 Correct 430 ms 36600 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 18276 KB Output is correct
2 Correct 2337 ms 132592 KB Output is correct
3 Correct 3513 ms 149912 KB Output is correct
4 Correct 955 ms 133248 KB Output is correct
5 Correct 4785 ms 156668 KB Output is correct
6 Correct 3576 ms 138484 KB Output is correct
7 Correct 1099 ms 59628 KB Output is correct
8 Correct 532 ms 60532 KB Output is correct
9 Correct 1291 ms 63048 KB Output is correct
10 Correct 1251 ms 58488 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 18552 KB Output is correct
2 Correct 386 ms 36672 KB Output is correct
3 Correct 422 ms 36600 KB Output is correct
4 Correct 425 ms 36732 KB Output is correct
5 Correct 446 ms 37104 KB Output is correct
6 Correct 311 ms 36628 KB Output is correct
7 Correct 538 ms 36752 KB Output is correct
8 Correct 426 ms 36748 KB Output is correct
9 Correct 451 ms 36848 KB Output is correct
10 Correct 312 ms 36564 KB Output is correct
11 Correct 430 ms 36600 KB Output is correct
12 Correct 24 ms 18276 KB Output is correct
13 Correct 2337 ms 132592 KB Output is correct
14 Correct 3513 ms 149912 KB Output is correct
15 Correct 955 ms 133248 KB Output is correct
16 Correct 4785 ms 156668 KB Output is correct
17 Correct 3576 ms 138484 KB Output is correct
18 Correct 1099 ms 59628 KB Output is correct
19 Correct 532 ms 60532 KB Output is correct
20 Correct 1291 ms 63048 KB Output is correct
21 Correct 1251 ms 58488 KB Output is correct
22 Correct 3182 ms 149244 KB Output is correct
23 Correct 3469 ms 151468 KB Output is correct
24 Correct 4803 ms 152376 KB Output is correct
25 Correct 5124 ms 154696 KB Output is correct
26 Correct 4350 ms 149048 KB Output is correct
27 Correct 5933 ms 169792 KB Output is correct
28 Correct 1273 ms 150908 KB Output is correct
29 Correct 4106 ms 148432 KB Output is correct
30 Correct 4273 ms 148348 KB Output is correct
31 Correct 4526 ms 153376 KB Output is correct
32 Correct 1551 ms 64072 KB Output is correct
33 Correct 560 ms 60740 KB Output is correct
34 Correct 903 ms 57576 KB Output is correct
35 Correct 1022 ms 57664 KB Output is correct
36 Correct 1159 ms 57852 KB Output is correct
37 Correct 1315 ms 55300 KB Output is correct