oj.uz

Submission #319717

# Submission time Handle Problem Language Result Execution time Memory
319717 2020-11-06T09:19:05 Z tushar_2658 Factories (JOI14_factories) C++14
100 / 100
 4191 ms 198360 KB 
#include "factories.h"
#include "bits/stdc++.h"
using namespace std;

const int maxn = 500005;
using ll = long long;
const ll inf = 1e18;

vector<pair<int, ll>> edges[maxn];
int n;
int sub[maxn], par[maxn], cent_dep[maxn];
int cent_vis[maxn];
ll mn[maxn], cent_dis[maxn][20];
stack<int> st;

void dfs(int x, int p, int d){
  sub[x] = 1;
  for(auto i : edges[x]){
    if(i.first != p){
      if(!cent_vis[i.first]){
        if(d){
          cent_dis[i.first][d - 1] = cent_dis[x][d - 1] + i.second;
        }
        dfs(i.first, x, d);
        sub[x] += sub[i.first];
      }
    }
  }
}

int find_centroid(int x, int p, int range){
  for(auto i : edges[x]){
    if(i.first != p && !cent_vis[i.first]){
      if(sub[i.first] > range)return find_centroid(i.first, x, range);
    }
  }return x;
}

void build(int x, int p, int d){
  dfs(x, -1, d);
  int c = find_centroid(x, -1, sub[x] / 2);
  par[c] = p;
  cent_vis[c] = 1;
  cent_dep[c] = d;
  for(auto i : edges[c]){
    if(!cent_vis[i.first]){
      cent_dis[i.first][d] = i.second;
      build(i.first, c, d + 1);
    }
  }
  cent_vis[c] = 0;
}

void upd(int x){
  int cur = x;
  while(cur != 0){
    mn[cur] = min(mn[cur], cent_dis[x][cent_dep[cur]]);
    st.push(cur);
    cur = par[cur];
  }
}

ll query(int x){
  ll ret = mn[x];
  int cur = x;
  while(cur != 0){
    ret = min(ret, mn[cur] + cent_dis[x][cent_dep[cur]]);
    cur = par[cur];
  }
  return ret;
}

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  for(int i = 0; i < N - 1; ++i){
    edges[A[i] + 1].push_back({B[i] + 1, D[i]});
    edges[B[i] + 1].push_back({A[i] + 1, D[i]});
  }
  build(1, 0, 0);
  for(int i = 1; i <= N; ++i){
    mn[i] = inf;
  }
}

long long Query(int S, int X[], int T, int Y[]) {
  for(int i = 0; i < S; ++i){
    upd(X[i] + 1);
  }
  ll ans = inf;
  for(int i = 0; i < T; ++i){
    ans = min(ans, query(Y[i] + 1));
  }
  while(!st.empty()){
    mn[st.top()] = inf;
    st.pop();
  }
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12540 KB Output is correct
2 Correct 375 ms 21348 KB Output is correct
3 Correct 413 ms 21624 KB Output is correct
4 Correct 415 ms 21600 KB Output is correct
5 Correct 454 ms 21864 KB Output is correct
6 Correct 291 ms 21348 KB Output is correct
7 Correct 408 ms 21348 KB Output is correct
8 Correct 425 ms 21604 KB Output is correct
9 Correct 447 ms 21908 KB Output is correct
10 Correct 292 ms 21476 KB Output is correct
11 Correct 410 ms 21348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12396 KB Output is correct
2 Correct 1919 ms 140652 KB Output is correct
3 Correct 2728 ms 144564 KB Output is correct
4 Correct 839 ms 138300 KB Output is correct
5 Correct 3511 ms 175076 KB Output is correct
6 Correct 2782 ms 164584 KB Output is correct
7 Correct 1012 ms 60656 KB Output is correct
8 Correct 527 ms 60368 KB Output is correct
9 Correct 1110 ms 65380 KB Output is correct
10 Correct 1030 ms 62052 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12540 KB Output is correct
2 Correct 375 ms 21348 KB Output is correct
3 Correct 413 ms 21624 KB Output is correct
4 Correct 415 ms 21600 KB Output is correct
5 Correct 454 ms 21864 KB Output is correct
6 Correct 291 ms 21348 KB Output is correct
7 Correct 408 ms 21348 KB Output is correct
8 Correct 425 ms 21604 KB Output is correct
9 Correct 447 ms 21908 KB Output is correct
10 Correct 292 ms 21476 KB Output is correct
11 Correct 410 ms 21348 KB Output is correct
12 Correct 10 ms 12396 KB Output is correct
13 Correct 1919 ms 140652 KB Output is correct
14 Correct 2728 ms 144564 KB Output is correct
15 Correct 839 ms 138300 KB Output is correct
16 Correct 3511 ms 175076 KB Output is correct
17 Correct 2782 ms 164584 KB Output is correct
18 Correct 1012 ms 60656 KB Output is correct
19 Correct 527 ms 60368 KB Output is correct
20 Correct 1110 ms 65380 KB Output is correct
21 Correct 1030 ms 62052 KB Output is correct
22 Correct 2400 ms 168492 KB Output is correct
23 Correct 2456 ms 171300 KB Output is correct
24 Correct 3507 ms 174012 KB Output is correct
25 Correct 3589 ms 176364 KB Output is correct
26 Correct 3495 ms 170800 KB Output is correct
27 Correct 4191 ms 198360 KB Output is correct
28 Correct 1080 ms 167484 KB Output is correct
29 Correct 3439 ms 170384 KB Output is correct
30 Correct 3507 ms 169636 KB Output is correct
31 Correct 3453 ms 170280 KB Output is correct
32 Correct 1145 ms 68524 KB Output is correct
33 Correct 529 ms 61136 KB Output is correct
34 Correct 793 ms 58132 KB Output is correct
35 Correct 853 ms 57904 KB Output is correct
36 Correct 999 ms 58836 KB Output is correct
37 Correct 1008 ms 58856 KB Output is correct