제출 #1046179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046179		juicy	Collapse (JOI18_collapse)	C++17	100 / 100	2826 ms	11848 KiB

collapse

#include <bits/stdc++.h>

#include "collapse.h"

using namespace std;

template<class T, size_t D>
ostream &operator << (ostream &os, array<T, D> u) {
  os << "{";
  for (size_t i = 0; i < D; ++i) {
    os << (i ? ", " : "") << u[i];
  }
  return os << "}";
} 

template<class T>
ostream &operator << (ostream &os, vector<T> u) {
  os << "{";
  for (int i = 0; i < u.size(); ++i) {
    os << (i ? ", " : "") << u[i];
  }
  return os << "}";
} 

void __print() {
  cerr << "]\n";
}

template<class T, class... V>
void __print(T t, V... v) {
  cerr << t;
  if (sizeof...(v)) {
    cerr << ", ";
  }
  __print(v...);
}

#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; __print(x);
#else 
#define debug(...) 42
#endif

vector<int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
  const int S = 320;

  int C = X.size(), Q = W.size();

  int cnt = 0;
  vector<int> lab(N, -1);
  vector<array<int, 2>> his;
  auto init = [&]() {
    fill(lab.begin(), lab.end(), -1);
    cnt = 0;
  };
  auto find = [&](int u) -> int {
    while (lab[u] >= 0) {
      u = lab[u];
    }
    return u;
  };
  auto unite = [&](int u, int v, bool keep) {
    u = find(u), v = find(v);
    if (u == v) {
      if (keep) {
        his.push_back({-1, -1});
      }
      return;
    }
    if (lab[u] > lab[v]) {
      swap(u, v);
    }
    if (keep) {
      his.push_back({v, lab[v]});
    }
    ++cnt;
    lab[u] += lab[v];
    lab[v] = u;
  };
  auto restore = [&]() {
    while (his.size()) {
      auto e = his.back(); his.pop_back();
      if (~e[0]) {
        --cnt;
        int &p = lab[e[0]];
        lab[p] -= e[1];
        p = e[1];
      }
    }
  };
  vector<array<int, 2>> comp;
  for (int i = 0; i < C; ++i) {
    if (X[i] > Y[i]) {
      swap(X[i], Y[i]);
    }
    comp.push_back({X[i], Y[i]});
  }
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  int M = comp.size();
  vector<int> pos(C);
  for (int i = 0; i < C; ++i) {
    T[i] ^= 1;
    pos[i] = lower_bound(comp.begin(), comp.end(), array<int, 2>{X[i], Y[i]}) - comp.begin();
  }
  vector<array<int, 3>> queries;
  vector<int> res(Q);
  for (int i = 0; i < Q; ++i) {
    queries.push_back({P[i], W[i], i});
    res[i] = N;
  }
  sort(queries.begin(), queries.end(), [&](const auto &u, const auto &v) {
    return u[1] < v[1];
  });
  vector<bool> tog(M), cur(M), nw(M);
  int ptr = 0;
  for (int i = 0; i < C; i += S) {
    int l = i, r = min(C - 1, i + S - 1);
    for (int j = l; j <= r; ++j) {
      tog[pos[j]] = 1;
    }
    vector<int> add;
    vector<array<int, 2>> cands;
    for (int j = 0; j < M; ++j) {
      if (!tog[j] && cur[j]) {
        cands.push_back(comp[j]);
      }
      if (tog[j]) {
        add.push_back(j);
      }
    }
    vector<array<int, 3>> ord;
    while (ptr < Q && queries[ptr][1] <= r) {
      ord.push_back(queries[ptr++]);
    }
    sort(ord.begin(), ord.end());
    sort(cands.begin(), cands.end(), [&](const auto &u, const auto &v) {
      return u[1] < v[1];
    });
    init();
    int k = 0;
    for (auto [x, d, id] : ord) {
      while (k < cands.size() && cands[k][1] <= x) {
        unite(cands[k][0], cands[k][1], 0);
        ++k;
      }
      for (int j = l; j <= d; ++j) {
        nw[pos[j]] = T[j];
      }
      for (int id : add) {
        if (nw[id] && comp[id][1] <= x) {
          unite(comp[id][0], comp[id][1], 1);
        }
        nw[id] = cur[id];
      }
      res[id] -= cnt;
      restore();
    }
    init();
    reverse(ord.begin(), ord.end());
    sort(cands.rbegin(), cands.rend());
    k = 0;
    for (auto [x, d, id] : ord) {
      while (k < cands.size() && cands[k][0] > x) {
        unite(cands[k][0], cands[k][1], 0);
        ++k;
      }
      for (int j = l; j <= d; ++j) {
        nw[pos[j]] = T[j];
      }
      for (int id : add) {
        if (nw[id] && comp[id][0] > x) {
          unite(comp[id][0], comp[id][1], 1);
        }
        nw[id] = cur[id];
      }
      res[id] -= cnt;
      restore();
    }
    for (int j = l; j <= r; ++j) {
      tog[pos[j]] = 0;
      cur[pos[j]] = T[j];
      nw[pos[j]] = cur[pos[j]];
    }
  }
  return res;
}

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

collapse.cpp: In function 'std::vector<int> simulateCollapse(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
collapse.cpp:143:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |       while (k < cands.size() && cands[k][1] <= x) {
      |              ~~^~~~~~~~~~~~~~
collapse.cpp:164:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |       while (k < cands.size() && cands[k][0] > x) {
      |              ~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 35 / 35