제출 #851199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851199		aymanrs	공장들 (JOI14_factories)	C++14	100 / 100	7424 ms	184392 KiB

factories

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67