oj.uz

Submission #851202

# Submission time Handle Problem Language Result Execution time Memory
851202 2023-09-18T20:31:05 Z aymanrs Factories (JOI14_factories) C++17
100 / 100
 7699 ms 183292 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
const int L = 19;
struct node {
  vector<pair<node*,int>> l;
  long long d;
  int depth;
  node* anc[L];
  node* par;
  bool v = false;
  int sz;
  long long cl = LONG_LONG_MAX;
};
node* lca(node* u, node* v){
  if(u->depth < v->depth) swap(u, v);
  int d = u->depth-v->depth;
  for(int i = 0;i < L;i++) if((d>>i)&1) u = u->anc[i];
  if(u == v) return u;
  for(int i = L-1;i >= 0;i--){
    if(u->anc[i] != v->anc[i]) {
      u = u->anc[i];
      v = v->anc[i];
    }
  }
  return u->anc[0];
}
int tot;
void ffs(node* n, node* p, long long d, int depth){
  n->d = d;
  n->depth = depth;
  n->anc[0] = p;
  for(int i = 1;i < L;i++) n->anc[i] = n->anc[i-1]->anc[i-1];
  for(auto [c, l] : n->l){
    if(c != p) ffs(c, n, d+l, depth+1);
  }
}
void dfs(node* n, node* p){
  n->sz = 1;
  for(auto [c, d] : n->l){
    if(c == p || c->v) continue;
    dfs(c, n);
    n->sz += c->sz;
  }
}
node* cent(node* n, node* p){
  for(auto [c,d]:n->l){
    if(c==p||c->v) continue;
    if(c->sz>tot/2){
      return cent(c, n);
    }
  }
  n->v = true;
  for(auto [c,d] : n->l){
    if(c->v) continue;
    dfs(c, n);
    tot = c->sz;
    node* ce = cent(c, n);
    ce->par = n;
  }
  return n;
}
vector<node> g;
void Init(int N, int A[], int B[], int D[]) {
  g.resize(N);
  for(int i = 0;i < N-1;i++){
    g[A[i]].l.emplace_back(&g[B[i]], D[i]);
    g[B[i]].l.emplace_back(&g[A[i]], D[i]);
  }
  tot = N;
  ffs(&g[0], &g[0], 0, 0);
  dfs(&g[0], NULL);
  cent(&g[0], NULL)->par = NULL;
}
long long Query(int S, int X[], int T, int Y[]) {
  vector<node*> t;
  #pragma GCC ivdep
  for(int i = 0;i < S;i++){
    node* x = &g[X[i]];
    while(x != NULL){
      t.push_back(x);
      x->cl = min(x->cl, x->d+g[X[i]].d-2*lca(&g[X[i]], x)->d);
      x = x->par;
    }
  }
  long long ans = LONG_LONG_MAX;
  #pragma GCC ivdep
  for(int i = 0;i < T;i++){
    node* y = &g[Y[i]];
    while(y != NULL){
      if(y->cl != LONG_LONG_MAX) ans = min(ans, y->d+g[Y[i]].d-2*lca(&g[Y[i]], y)->d+y->cl);
      y = y->par;
    }
  }
  for(node* n : t) n->cl = LONG_LONG_MAX;
  return ans;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16984 KB Output is correct
2 Correct 429 ms 22476 KB Output is correct
3 Correct 867 ms 22620 KB Output is correct
4 Correct 719 ms 23244 KB Output is correct
5 Correct 1050 ms 22972 KB Output is correct
6 Correct 171 ms 22352 KB Output is correct
7 Correct 883 ms 22584 KB Output is correct
8 Correct 879 ms 22352 KB Output is correct
9 Correct 1037 ms 22888 KB Output is correct
10 Correct 174 ms 22364 KB Output is correct
11 Correct 865 ms 22320 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 1396 ms 154952 KB Output is correct
3 Correct 2802 ms 158100 KB Output is correct
4 Correct 548 ms 152776 KB Output is correct
5 Correct 3987 ms 172216 KB Output is correct
6 Correct 3050 ms 158100 KB Output is correct
7 Correct 1950 ms 48572 KB Output is correct
8 Correct 333 ms 47808 KB Output is correct
9 Correct 2246 ms 50512 KB Output is correct
10 Correct 1816 ms 49016 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16984 KB Output is correct
2 Correct 429 ms 22476 KB Output is correct
3 Correct 867 ms 22620 KB Output is correct
4 Correct 719 ms 23244 KB Output is correct
5 Correct 1050 ms 22972 KB Output is correct
6 Correct 171 ms 22352 KB Output is correct
7 Correct 883 ms 22584 KB Output is correct
8 Correct 879 ms 22352 KB Output is correct
9 Correct 1037 ms 22888 KB Output is correct
10 Correct 174 ms 22364 KB Output is correct
11 Correct 865 ms 22320 KB Output is correct
12 Correct 3 ms 16984 KB Output is correct
13 Correct 1396 ms 154952 KB Output is correct
14 Correct 2802 ms 158100 KB Output is correct
15 Correct 548 ms 152776 KB Output is correct
16 Correct 3987 ms 172216 KB Output is correct
17 Correct 3050 ms 158100 KB Output is correct
18 Correct 1950 ms 48572 KB Output is correct
19 Correct 333 ms 47808 KB Output is correct
20 Correct 2246 ms 50512 KB Output is correct
21 Correct 1816 ms 49016 KB Output is correct
22 Correct 2048 ms 161792 KB Output is correct
23 Correct 2007 ms 170428 KB Output is correct
24 Correct 5385 ms 173020 KB Output is correct
25 Correct 5320 ms 172876 KB Output is correct
26 Correct 5347 ms 157160 KB Output is correct
27 Correct 7699 ms 183292 KB Output is correct
28 Correct 709 ms 154728 KB Output is correct
29 Correct 4969 ms 156752 KB Output is correct
30 Correct 5180 ms 156240 KB Output is correct
31 Correct 5140 ms 156692 KB Output is correct
32 Correct 2958 ms 65036 KB Output is correct
33 Correct 334 ms 48764 KB Output is correct
34 Correct 925 ms 47680 KB Output is correct
35 Correct 853 ms 47424 KB Output is correct
36 Correct 2243 ms 48388 KB Output is correct
37 Correct 2077 ms 48124 KB Output is correct