oj.uz

Submission #197504

# Submission time Handle Problem Language Result Execution time Memory
197504 2020-01-21T13:18:05 Z handlename Factories (JOI14_factories) C++17
100 / 100
 4209 ms 181336 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
#define mp make_pair
#define pb push_back
int n;
vector<pair<int,int> > adj[500001];
int sub[500001],lvl[500001],par[500001];
long long ans[500001];
long long dist[500001][19];
stack<int> st;
int dfs1(int u,int p,int l){
    sub[u]=1; // Subtree size is 1
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        // Already added to centroid tree
        if (i.first==p) continue;
        if (l>0) dist[i.first][l-1]=dist[u][l-1]+i.second;
        sub[u]+=dfs1(i.first,u,l);
        // Increase size of subtree
    }
    return sub[u];
}
int dfs2(int u,int p,int sn){
    // Pass in the size of the subtree
    for (auto i:adj[u]){
        if (lvl[i.first]!=-1) continue;
        // Already added to centroid tree
        if (i.first==p) continue;
        if (sub[i.first]>sn/2){
            return dfs2(i.first,u,sn);
        }
    }
    return u; // No child has size more than n/2 , hence you are the centroid
}
// Building from node u, with a parent p and level l
void build(int u,int p,int l){
    int cn=dfs1(u,p,l);
    int cent=dfs2(u,p,cn);
    if (p==-1) p=cent;
    par[cent]=p;
    lvl[cent]=l;
    for (auto i:adj[cent]){
        if (lvl[i.first]!=-1) continue;
        dist[i.first][l]=i.second;
        build(i.first,cent,l+1);
    }
}
void upd(int x){
    int l=lvl[x];
    int y=x;
    while (l!=-1){
        ans[y]=min(ans[y],dist[x][l]);
        // Check the shortest distance against the distance between the current node
        st.push(y);
        y=par[y];
        // Traverse up the centroid tree
        l--;
        // Keep track of which parent we are on
    }
}
long long qry(int x){
    long long res=1e16;
    int l=lvl[x];
    int y=x;
    while (l!=-1){
        res=min(res,ans[y]+dist[x][l]);
        y=par[y];
        l--;
    }
    return res;
}
void Init(int N, int A[], int B[], int D[]) {
    n=N;
    for (int i=0;i<n-1;i++){
        adj[A[i]].pb(mp(B[i],D[i]));
        adj[B[i]].pb(mp(A[i],D[i]));
    }
    memset(lvl,-1,sizeof(lvl));
    build(0,-1,0);
    for (int i=0;i<n;i++) ans[i]=1e16;
}
long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0;i<S;i++) upd(X[i]);
    long long res=1e16;
    for (int i=0;i<T;i++) res=min(res,qry(Y[i]));
    while (!st.empty()){
        ans[st.top()]=1e16;
        st.pop();
    }
    return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14584 KB Output is correct
2 Correct 373 ms 32608 KB Output is correct
3 Correct 415 ms 32760 KB Output is correct
4 Correct 410 ms 32764 KB Output is correct
5 Correct 437 ms 33164 KB Output is correct
6 Correct 306 ms 32664 KB Output is correct
7 Correct 407 ms 32760 KB Output is correct
8 Correct 418 ms 32736 KB Output is correct
9 Correct 438 ms 33032 KB Output is correct
10 Correct 307 ms 32636 KB Output is correct
11 Correct 409 ms 32668 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14456 KB Output is correct
2 Correct 2147 ms 146556 KB Output is correct
3 Correct 2431 ms 148148 KB Output is correct
4 Correct 879 ms 146780 KB Output is correct
5 Correct 3459 ms 177300 KB Output is correct
6 Correct 2540 ms 150384 KB Output is correct
7 Correct 1014 ms 59228 KB Output is correct
8 Correct 518 ms 59880 KB Output is correct
9 Correct 1222 ms 63728 KB Output is correct
10 Correct 976 ms 60792 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 14584 KB Output is correct
2 Correct 373 ms 32608 KB Output is correct
3 Correct 415 ms 32760 KB Output is correct
4 Correct 410 ms 32764 KB Output is correct
5 Correct 437 ms 33164 KB Output is correct
6 Correct 306 ms 32664 KB Output is correct
7 Correct 407 ms 32760 KB Output is correct
8 Correct 418 ms 32736 KB Output is correct
9 Correct 438 ms 33032 KB Output is correct
10 Correct 307 ms 32636 KB Output is correct
11 Correct 409 ms 32668 KB Output is correct
12 Correct 17 ms 14456 KB Output is correct
13 Correct 2147 ms 146556 KB Output is correct
14 Correct 2431 ms 148148 KB Output is correct
15 Correct 879 ms 146780 KB Output is correct
16 Correct 3459 ms 177300 KB Output is correct
17 Correct 2540 ms 150384 KB Output is correct
18 Correct 1014 ms 59228 KB Output is correct
19 Correct 518 ms 59880 KB Output is correct
20 Correct 1222 ms 63728 KB Output is correct
21 Correct 976 ms 60792 KB Output is correct
22 Correct 2262 ms 155640 KB Output is correct
23 Correct 2377 ms 157808 KB Output is correct
24 Correct 3386 ms 159336 KB Output is correct
25 Correct 3285 ms 162124 KB Output is correct
26 Correct 3336 ms 156448 KB Output is correct
27 Correct 4209 ms 181336 KB Output is correct
28 Correct 1109 ms 157616 KB Output is correct
29 Correct 3218 ms 156140 KB Output is correct
30 Correct 3160 ms 155492 KB Output is correct
31 Correct 3163 ms 156304 KB Output is correct
32 Correct 1282 ms 66780 KB Output is correct
33 Correct 539 ms 60736 KB Output is correct
34 Correct 831 ms 57104 KB Output is correct
35 Correct 830 ms 56952 KB Output is correct
36 Correct 1029 ms 57720 KB Output is correct
37 Correct 1051 ms 57824 KB Output is correct