oj.uz

Submission #851198

# Submission time Handle Problem Language Result Execution time Memory
851198 2023-09-18T20:26:18 Z aymanrs Factories (JOI14_factories) C++14
33 / 100
 8000 ms 216948 KB 
#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:34:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |   for(auto [c, l] : n->l){
      |            ^
factories.cpp: In function 'void dfs(node*, node*)':
factories.cpp:40:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   40 |   for(auto [c, d] : n->l){
      |            ^
factories.cpp: In function 'node* cent(node*, node*)':
factories.cpp:47:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |   for(auto [c,d]:n->l){
      |            ^
factories.cpp:54:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   54 |   for(auto [c,d] : n->l){
      |            ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16984 KB Output is correct
2 Correct 534 ms 32192 KB Output is correct
3 Correct 996 ms 31844 KB Output is correct
4 Correct 820 ms 32820 KB Output is correct
5 Correct 1221 ms 32464 KB Output is correct
6 Correct 201 ms 31832 KB Output is correct
7 Correct 986 ms 32112 KB Output is correct
8 Correct 1004 ms 32080 KB Output is correct
9 Correct 1195 ms 32560 KB Output is correct
10 Correct 194 ms 31824 KB Output is correct
11 Correct 981 ms 31844 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 1574 ms 173616 KB Output is correct
3 Correct 3108 ms 176912 KB Output is correct
4 Correct 615 ms 170988 KB Output is correct
5 Correct 4846 ms 201388 KB Output is correct
6 Correct 3341 ms 178184 KB Output is correct
7 Correct 2044 ms 62688 KB Output is correct
8 Correct 346 ms 61724 KB Output is correct
9 Correct 2691 ms 65864 KB Output is correct
10 Correct 2021 ms 63484 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 16984 KB Output is correct
2 Correct 534 ms 32192 KB Output is correct
3 Correct 996 ms 31844 KB Output is correct
4 Correct 820 ms 32820 KB Output is correct
5 Correct 1221 ms 32464 KB Output is correct
6 Correct 201 ms 31832 KB Output is correct
7 Correct 986 ms 32112 KB Output is correct
8 Correct 1004 ms 32080 KB Output is correct
9 Correct 1195 ms 32560 KB Output is correct
10 Correct 194 ms 31824 KB Output is correct
11 Correct 981 ms 31844 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 1574 ms 173616 KB Output is correct
14 Correct 3108 ms 176912 KB Output is correct
15 Correct 615 ms 170988 KB Output is correct
16 Correct 4846 ms 201388 KB Output is correct
17 Correct 3341 ms 178184 KB Output is correct
18 Correct 2044 ms 62688 KB Output is correct
19 Correct 346 ms 61724 KB Output is correct
20 Correct 2691 ms 65864 KB Output is correct
21 Correct 2021 ms 63484 KB Output is correct
22 Correct 2422 ms 186156 KB Output is correct
23 Correct 2179 ms 194160 KB Output is correct
24 Correct 5796 ms 197452 KB Output is correct
25 Correct 5674 ms 198196 KB Output is correct
26 Correct 5511 ms 182988 KB Output is correct
27 Execution timed out 8087 ms 216948 KB Time limit exceeded
28 Halted 0 ms 0 KB -