Submission #851186

#	Time	Username	Problem	Language	Result	Execution time	Memory
851186		aymanrs	Factories (JOI14_factories)	C++17	0 / 100	6 ms	16984 KiB

factories

#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;
  long long dpar = 0;
  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;
    ce->dpar = n->d+ce->d - 2*lca(n, ce)->d;
  }
  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;
  N = 1;

}
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]];
    long long cur = 0;
    while(x != NULL){
      if(x->cl < cur) break;
      t.push_back(x);
      x->cl = cur;
      cur += x->dpar;
      x = x->par;
    }
  }
  long long ans = LONG_LONG_MAX;
  for(int i = 0;i < T;i++){
    node* y = &g[Y[i]];
    long long cur = 0;
    while(y != NULL){
      if(y->cl != LONG_LONG_MAX) ans = min(ans, cur+y->cl);
      cur += y->dpar;
      y = y->par;
    }
  }
  for(node* n : t) n->cl = LONG_LONG_MAX;
  return ans;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67