제출 #861782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861782		mgl_diamond	공장들 (JOI14_factories)	C++17	100 / 100	1877 ms	156024 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define file "input"

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);

  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const ll BIG = 1e18;
const int N = 5e5+5, LOG = 19;
int n, q;
vector<ii> graph[N];

int cnt, anc[N][LOG], st[N], en[N];
ll distb[N], distr[N], curpar[N], wei[N];
vector<int> node;
bool red[N], blue[N];

void dfs_prep(int u, int p) {
//  cout << u << "\n";
  anc[u][0] = p;
  foru(i, 1, LOG-1) anc[u][i] = anc[anc[u][i-1]][i-1];
  st[u] = ++cnt;
  fore(x, graph[u]) if (x.first != p) {
    wei[x.first] = wei[u] + x.second;
    dfs_prep(x.first, u);
  }
  en[u] = cnt;
}

bool isanc(int u, int v) {
  return st[u] <= st[v] && en[v] <= en[u];
}

int lca(int u, int v) {
  if (isanc(u, v)) return u;
  ford(i, LOG-1, 0) {
    int tmp = anc[u][i];
    if (!isanc(tmp, v)) u = tmp;
  }
  return anc[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
  n = N;
  foru(i, 0, n-2) {
    graph[A[i]+1].emplace_back(B[i]+1, D[i]);
    graph[B[i]+1].emplace_back(A[i]+1, D[i]);
  }

  en[0] = n+1;
  dfs_prep(1, 0);
}

long long Query(int S, int X[], int T, int Y[]) {
  foru(i, 0, S-1) {
    int v = X[i]+1;
    node.push_back(v);
    red[v] = 1;
  }

  foru(i, 0, T-1) {
    int v = Y[i]+1;
    node.push_back(v);
    blue[v] = 1;
  }

  sort(all(node), [&](int x, int y){
    return st[x] < st[y];
  });

  int m = sz(node)-2;
  foru(i, 0, m) node.push_back(lca(node[i], node[i+1]));

  sort(all(node), [&](int x, int y){
    return st[x] < st[y];
  });
  node.resize(unique(all(node)) - node.begin());

  stack<int> tmp;
  fore(u, node) {
    distb[u] = distr[u] = BIG;
    curpar[u] = 0;
    while (!tmp.empty()) {
      if (en[tmp.top()] < st[u]) tmp.pop();
      else {
        curpar[u] = tmp.top();
        break;
      }
    }
    tmp.push(u);
  }

  ll ans = BIG;
  ford(i, sz(node)-1, 0) {
    int u = node[i];
//    cout << u << "\n";
    if (blue[u]) distb[u] = 0;
    if (red[u]) distr[u] = 0;
    ans = min(ans, distb[u] + distr[u]);

    if (curpar[u] > 0) {
      distb[curpar[u]] = min(distb[curpar[u]], distb[u] + wei[u] - wei[curpar[u]]);
      distr[curpar[u]] = min(distr[curpar[u]], distr[u] + wei[u] - wei[curpar[u]]);
    }
  }

  fore(u, node) {
    blue[u] = red[u] = 0;
  }
  node.clear();

  return ans;
}

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

factories.cpp: In function 'void setIO()':
factories.cpp:19:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:20:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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