oj.uz

Submission #851199

# Submission time Handle Problem Language Result Execution time Memory
851199 2023-09-18T20:28:14 Z aymanrs Factories (JOI14_factories) C++14
100 / 100
 7424 ms 184392 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;
  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;
  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;
}

Compilation message

factories.cpp: In function 'void ffs(node*, node*, long long int, int)':
factories.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   36 |   for(auto [c, l] : n->l){
      |            ^
factories.cpp: In function 'void dfs(node*, node*)':
factories.cpp:42:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   42 |   for(auto [c, d] : n->l){
      |            ^
factories.cpp: In function 'node* cent(node*, node*)':
factories.cpp:49:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   49 |   for(auto [c,d]:n->l){
      |            ^
factories.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   56 |   for(auto [c,d] : n->l){
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16984 KB Output is correct
2 Correct 424 ms 29908 KB Output is correct
3 Correct 866 ms 29776 KB Output is correct
4 Correct 729 ms 30832 KB Output is correct
5 Correct 1016 ms 30296 KB Output is correct
6 Correct 180 ms 29780 KB Output is correct
7 Correct 859 ms 30024 KB Output is correct
8 Correct 899 ms 29992 KB Output is correct
9 Correct 1048 ms 30460 KB Output is correct
10 Correct 179 ms 29776 KB Output is correct
11 Correct 860 ms 29776 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 1373 ms 164764 KB Output is correct
3 Correct 2745 ms 166936 KB Output is correct
4 Correct 571 ms 162576 KB Output is correct
5 Correct 4038 ms 181584 KB Output is correct
6 Correct 2941 ms 167576 KB Output is correct
7 Correct 1983 ms 55760 KB Output is correct
8 Correct 339 ms 54976 KB Output is correct
9 Correct 2101 ms 57812 KB Output is correct
10 Correct 1908 ms 56196 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 424 ms 29908 KB Output is correct
3 Correct 866 ms 29776 KB Output is correct
4 Correct 729 ms 30832 KB Output is correct
5 Correct 1016 ms 30296 KB Output is correct
6 Correct 180 ms 29780 KB Output is correct
7 Correct 859 ms 30024 KB Output is correct
8 Correct 899 ms 29992 KB Output is correct
9 Correct 1048 ms 30460 KB Output is correct
10 Correct 179 ms 29776 KB Output is correct
11 Correct 860 ms 29776 KB Output is correct
12 Correct 4 ms 16984 KB Output is correct
13 Correct 1373 ms 164764 KB Output is correct
14 Correct 2745 ms 166936 KB Output is correct
15 Correct 571 ms 162576 KB Output is correct
16 Correct 4038 ms 181584 KB Output is correct
17 Correct 2941 ms 167576 KB Output is correct
18 Correct 1983 ms 55760 KB Output is correct
19 Correct 339 ms 54976 KB Output is correct
20 Correct 2101 ms 57812 KB Output is correct
21 Correct 1908 ms 56196 KB Output is correct
22 Correct 2123 ms 174140 KB Output is correct
23 Correct 1987 ms 182208 KB Output is correct
24 Correct 5201 ms 184392 KB Output is correct
25 Correct 5155 ms 173204 KB Output is correct
26 Correct 5142 ms 157592 KB Output is correct
27 Correct 7424 ms 183312 KB Output is correct
28 Correct 708 ms 179380 KB Output is correct
29 Correct 4847 ms 181152 KB Output is correct
30 Correct 5021 ms 180884 KB Output is correct
31 Correct 5220 ms 181300 KB Output is correct
32 Correct 2683 ms 79516 KB Output is correct
33 Correct 336 ms 62612 KB Output is correct
34 Correct 862 ms 61072 KB Output is correct
35 Correct 851 ms 61008 KB Output is correct
36 Correct 2166 ms 62016 KB Output is correct
37 Correct 2025 ms 61732 KB Output is correct