#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int dsu[N], sz[N];
int comps;
vector<int> g[N];
bool vis[N];
int added;
void dfs(int v) {
vis[v] = 1;
for (int u : g[v]) {
if (!vis[u]) {
++added;
dfs(u);
}
}
}
int get(int v) {
return dsu[v] == v ? v : dsu[v] = get(dsu[v]);
}
void unite(int v, int u) {
v = get(v);
u = get(u);
if (v == u) return;
--comps;
if (sz[v] > sz[u]) swap(v, u);
sz[u] += sz[v];
dsu[v] = u;
}
void init(int n) {
for (int i = 0; i < n; ++i) {
dsu[i] = i;
sz[i] = 1;
}
comps = n;
}
vector<int> solve(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
int c = t.size(), q = w.size();
for (int i = 0; i < c; ++i) {
if (x[i] > y[i]) swap(x[i], y[i]);
}
vector<int> when(c, c);
map<pair<int, int>, int> lst;
for (int i = 0; i < c; ++i) {
if (t[i] == 0) {
lst[{x[i], y[i]}] = i;
} else {
when[lst[{x[i], y[i]}]] = i;
}
}
int sq = sqrt(c);
vector<int> d(q, 0);
for (int l = 0; l < c; l += sq) {
int r = min(c, l + sq);
vector<int> here;
vector<vector<int>> by_y(n + 1), by_p(n + 1);
for (int i = 0; i < l; ++i) {
if (t[i] == 1) continue;
if (when[i] >= r) {
by_y[y[i]].push_back(i);
} else {
here.push_back(i);
}
}
for (int i = l; i < r; ++i) {
if (t[i] == 0) here.push_back(i);
}
for (int i = 0; i < q; ++i) {
if (w[i] >= l && w[i] < r) by_p[p[i]].push_back(i);
}
init(n);
for (int i = 0; i <= n; ++i) {
for (int id : by_p[i]) {
d[id] = comps;
vector<pair<int, int>> edges;
for (int edge_id : here) {
if (edge_id <= w[id] && w[id] < when[edge_id] && y[edge_id] < i) edges.push_back({get(x[edge_id]), get(y[edge_id])});
}
for (auto [u, v] : edges) {
g[u] = g[v] = {};
vis[u] = vis[v] = 0;
}
for (auto [u, v] : edges) {
g[u].push_back(v);
g[v].push_back(u);
}
added = 0;
for (auto [u, v] : edges) {
if (!vis[u]) dfs(u);
if (!vis[v]) dfs(v);
}
d[id] -= added;
}
for (int id : by_y[i]) unite(x[id], y[id]);
}
}
return d;
}
vector<int> simulateCollapse(int n, vector<int> t, vector<int> x, vector<int> y, vector<int> w, vector<int> p) {
int c = t.size(), q = w.size();
for (int i = 0; i < q; ++i) ++p[i];
auto d1 = solve(n, t, x, y, w, p);
for (int i = 0; i < c; ++i) {
x[i] = n - x[i] - 1;
y[i] = n - y[i] - 1;
}
for (int i = 0; i < q; ++i) p[i] = n - p[i];
auto d2 = solve(n, t, x, y, w, p);
vector<int> d(q);
for (int i = 0; i < q; ++i) d[i] = d1[i] + d2[i];
return d;
}
#ifndef EVAL
int main() {
freopen("input.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int n, c, q;
cin >> n >> c >> q;
vector<int> t(c), x(c), y(c);
for (int i = 0; i < c; ++i) {
cin >> t[i] >> x[i] >> y[i];
}
vector<int> w(q), p(q);
for (int i = 0; i < q; ++i) {
cin >> w[i] >> p[i];
}
auto d = simulateCollapse(n, t, x, y, w, p);
for (int i = 0; i < q; ++i) cout << d[i] << '\n';
return 0;
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
3052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
6764 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
6732 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
31 ms |
3052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
