제출 #1046179

#제출 시각아이디문제언어결과실행 시간메모리
1046179juicyCollapse (JOI18_collapse)C++17
100 / 100
2826 ms11848 KiB
#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) {
      |              ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...