#include "collapse.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;
const int MAX_N = (1 << 17);
const int MAX_UF = 159;
const int BACKET = 1009;
class SuperiorRankUnionFind {
public:
int query = 0, numedge = 0;
vector<int> par, ranks;
vector<pair<int, int>> G_par, G_ranks;
void init(int sz) {
query = 0; numedge = 0;
par.resize(sz, -1);
ranks.resize(sz, -1);
G_par.resize(MAX_N, make_pair(-1, -1));
G_ranks.resize(MAX_N, make_pair(-1, -1));
}
int root(int pos) {
while (par[pos] != -1) {
pos = par[pos];
}
return pos;
}
void unite(int u, int v) {
query++;
u = root(u); v = root(v);
if (u == v) return;
if (ranks[u] > ranks[v]) swap(u, v);
G_par[query] = make_pair(u, par[u]);
par[u] = v;
G_ranks[query] = make_pair(u, ranks[u]);
ranks[u] = v;
numedge++;
}
void reversi() {
if (G_par[query] != make_pair(-1, -1)) {
pair<int, int> E = G_par[query];
par[E.first] = E.second;
}
if (G_ranks[query] != make_pair(-1, -1)) {
pair<int, int> E = G_ranks[query];
ranks[E.first] = E.second;
}
if (G_par[query] != make_pair(-1, -1)) numedge--;
G_par[query] = make_pair(-1, -1);
G_ranks[query] = make_pair(-1, -1);
query--;
}
};
int SIZE_ = 1;
int N, C, Q, T[MAX_N], X[MAX_N], Y[MAX_N], W[MAX_N], P[MAX_N], ans[MAX_N];
vector<pair<int, int>> Question[MAX_N];
vector<pair<int, int>> G[MAX_N * 2];
map<pair<int, int>, int> Map;
SuperiorRankUnionFind UF[209]; int cnts, el[209], er[209], deg[MAX_N];
vector<tuple<int, int, int, int>> PossibleEdge[209];
void add_(int l, int r, pair<int, int>x, int a, int b, int u) {
if (l <= a && b <= r) {
G[u].push_back(x);
return;
}
if (r <= a || b <= l) return;
add_(l, r, x, a, (a + b) >> 1, u * 2);
add_(l, r, x, (a + b) >> 1, b, u * 2 + 1);
}
void add_edge(int l, int r, pair<int, int>x) {
for (int i = 1; i <= cnts; i++) {
if ((el[i] <= x.first && x.first <= er[i]) || (el[i] <= x.second && x.second <= er[i])) {
PossibleEdge[i].push_back(make_tuple(x.first, x.second, l, r));
}
}
add_(l, r, x, 0, SIZE_, 1);
}
void dfs(int u) {
// 辺の追加
for (int i = 1; i <= cnts; i++) {
for (pair<int, int> edge : G[u]) {
if (edge.second <= el[i] || er[i] < edge.first) UF[i].unite(edge.first, edge.second);
}
}
// 探索続行 (u < SIZE)、判定 (u >= SIZE)
if (u < SIZE_) {
dfs(u * 2);
dfs(u * 2 + 1);
}
else {
for (pair<int, int> que : Question[u - SIZE_]) {
int p = que.first, id = -1;
for (int i = 1; i <= cnts; i++) {
if (el[i] <= p && p <= er[i]) id = i;
}
int cntv = 0;
for (int i = 0; i < PossibleEdge[id].size(); i++) {
tuple<int, int, int, int> H = PossibleEdge[id][i];
if (get<2>(H) <= u - SIZE_ && u - SIZE_ <= get<3>(H) && (get<1>(H) <= p || p < get<0>(H))) {
UF[id].unite(get<0>(H), get<1>(H)); cntv++;
}
}
ans[que.second] = N - UF[id].numedge;
for (int i = 1; i <= cntv; i++) UF[id].reversi();
}
}
// 辺の削除
for (int i = 1; i <= cnts; i++) {
int cntv = 0;
for (pair<int, int> edge : G[u]) {
if (edge.second < el[i] || er[i] < edge.first) cntv++;
}
for (int j = 0; j < cntv; j++) UF[i].reversi();
}
}
vector<int> solve() {
// Step 1 : 幅を決める
for (int i = 1; i <= C; i++) { deg[X[i]]++; deg[Y[i]]++; }
int sum1 = 0, id = 1;
for (int i = 1; i <= N; i++) {
sum1 += deg[i];
if (sum1 + deg[i + 1] > BACKET || i == N) {
cnts++;
el[cnts] = id;
er[cnts] = i;
sum1 = 0; id = i + 1;
}
}
// Step 2 : 前準備
while (SIZE_ <= C) SIZE_ *= 2;
for (int i = 1; i <= C; i++) {
if (T[i] == 0) {
Map[make_pair(X[i], Y[i])] = i;
}
if (T[i] == 1) {
int S = Map[make_pair(X[i], Y[i])];
add_edge(S, i, make_pair(X[i], Y[i]));
Map[make_pair(X[i], Y[i])] = 0;
}
}
for (int i = 1; i <= C; i++) {
if (Map[make_pair(X[i], Y[i])] != 0) {
int S = Map[make_pair(X[i], Y[i])];
add_edge(S, C + 1, make_pair(X[i], Y[i]));
Map[make_pair(X[i], Y[i])] = 0;
}
}
// Step 3 : 質問の設定
for (int i = 1; i <= Q; i++) {
Question[W[i]].push_back(make_pair(P[i], i));
}
for (int i = 1; i <= cnts; i++) UF[i].init(N + 2);
// Step 4 : 探索
dfs(1);
// Step 5 : 最終決定
vector<int>FinalAns;
for (int i = 1; i <= Q; i++) FinalAns.push_back(ans[i]);
return FinalAns;
}
vector<int> simulateCollapse(int N1, vector<int>T1, vector<int>X1, vector<int>Y1, vector<int>W1, vector<int>P1) {
N = N1; C = T1.size(); Q = W1.size();
for (int i = 1; i <= C; i++) T[i] = T1[i - 1];
for (int i = 1; i <= C; i++) { X[i] = X1[i - 1]; X[i]++; }
for (int i = 1; i <= C; i++) { Y[i] = Y1[i - 1]; Y[i]++; }
for (int i = 1; i <= Q; i++) { W[i] = W1[i - 1]; W[i]++; }
for (int i = 1; i <= Q; i++) { P[i] = P1[i - 1]; P[i]++; }
for (int i = 1; i <= C; i++) { if (X[i] > Y[i]) swap(X[i], Y[i]); }
return solve();
}
Compilation message
collapse.cpp: In function 'void dfs(int)':
collapse.cpp:109:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < PossibleEdge[id].size(); i++) {
~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
12024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
16108 KB |
Output is correct |
| 2 |
Incorrect |
45 ms |
16116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
16280 KB |
Output is correct |
| 2 |
Correct |
48 ms |
15960 KB |
Output is correct |
| 3 |
Correct |
59 ms |
16120 KB |
Output is correct |
| 4 |
Correct |
74 ms |
16408 KB |
Output is correct |
| 5 |
Correct |
1316 ms |
16244 KB |
Output is correct |
| 6 |
Correct |
2205 ms |
36300 KB |
Output is correct |
| 7 |
Execution timed out |
15032 ms |
374264 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
29 ms |
14456 KB |
Output is correct |
| 2 |
Incorrect |
13 ms |
12024 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
