oj.uz

Submission #319714

# Submission time Handle Problem Language Result Execution time Memory
319714 2020-11-06T08:56:54 Z tushar_2658 Factories (JOI14_factories) C++14
15 / 100
 8000 ms 257840 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;
ll dis[maxn], sparse[maxn][20];
int depth[maxn];

void dfs(int x, int p, ll c){
  dis[x] = c;
  depth[x] = depth[p] + 1;
  sparse[x][0] = p;
  for(auto i : edges[x]){
    if(i.first != p){
      dfs(i.first, x, c + i.second);
    }
  }
} 

void build_lca(){
  for(int j = 1; j < 20; ++j){
    for(int i = 1; i <= n; ++i){
      if(sparse[i][j - 1] != 0){
        sparse[i][j] = sparse[sparse[i][j - 1]][j - 1];
      }
    }
  }
}

int LCA(int x, int y){
  if(depth[x] < depth[y])swap(x, y);
  for(int i = 19; i >= 0; --i){
    if(depth[x] - (1 << i) >= depth[y]){
      x = sparse[x][i];
    }
  }
  if(x == y)return x;
  for(int i = 19; i >= 0; --i){
    if(sparse[x][i] != sparse[y][i] && sparse[x][i] != 0 && sparse[y][i] != 0){
      x = sparse[x][i];
      y = sparse[y][i];
    }
  }
  return sparse[x][0];
}

ll DIS(int x, int y){
  return dis[x] + dis[y] - (2 * dis[LCA(x, y)]);
}

int sub[maxn], par[maxn], cent_dep[maxn];
int cent_vis[maxn];

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

ll mn[maxn], cent_dis[maxn][20];

void calc(int x){
  int cur = x, lvl = 0;
  while(cur != 0){
    cent_dis[x][lvl] = DIS(cur, x);
    cur = par[cur];
    ++lvl;
  }
}

stack<int> st;

void upd(int x){
  int cur = x;
  while(cur != 0){
    mn[cur] = min(mn[cur], cent_dis[x][cent_dep[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[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]});
  }
  dfs(1, 1, 0);
  build_lca();
  build(1, 0, 1);
  for(int i = 1; i <= N; ++i){
    calc(i);
  }
  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 12780 KB Output is correct
2 Correct 378 ms 24924 KB Output is correct
3 Correct 414 ms 24932 KB Output is correct
4 Correct 410 ms 25188 KB Output is correct
5 Correct 449 ms 25448 KB Output is correct
6 Correct 292 ms 24932 KB Output is correct
7 Correct 402 ms 25060 KB Output is correct
8 Correct 412 ms 25188 KB Output is correct
9 Correct 435 ms 25340 KB Output is correct
10 Correct 288 ms 25056 KB Output is correct
11 Correct 403 ms 24924 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12428 KB Output is correct
2 Correct 2889 ms 225012 KB Output is correct
3 Correct 6155 ms 228952 KB Output is correct
4 Correct 1049 ms 222652 KB Output is correct
5 Execution timed out 8031 ms 257840 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12780 KB Output is correct
2 Correct 378 ms 24924 KB Output is correct
3 Correct 414 ms 24932 KB Output is correct
4 Correct 410 ms 25188 KB Output is correct
5 Correct 449 ms 25448 KB Output is correct
6 Correct 292 ms 24932 KB Output is correct
7 Correct 402 ms 25060 KB Output is correct
8 Correct 412 ms 25188 KB Output is correct
9 Correct 435 ms 25340 KB Output is correct
10 Correct 288 ms 25056 KB Output is correct
11 Correct 403 ms 24924 KB Output is correct
12 Correct 10 ms 12428 KB Output is correct
13 Correct 2889 ms 225012 KB Output is correct
14 Correct 6155 ms 228952 KB Output is correct
15 Correct 1049 ms 222652 KB Output is correct
16 Execution timed out 8031 ms 257840 KB Time limit exceeded
17 Halted 0 ms 0 KB -