| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1261828 | Bui_Quoc_Cuong | Collapse (JOI18_collapse) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
// #include "collapse.h"
using namespace std;
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define all(a) a.begin(), a.end()
#define pb push_back
#define fi first
#define se second
const int maxN = 1e5 + 5;
int n, m, q;
array <int, 3> edges[maxN];
array <int, 2> Q[maxN];
void init() {
cin >> n >> m >> q;
FOR(i, 1, m) {
cin >> edges[i][0] >> edges[i][1] >> edges[i][2];
edges[i][1]++; edges[i][2]++;
if (edges[i][1] > edges[i][2]) swap(edges[i][1], edges[i][2]);
}
FOR(i, 1, q) {
cin >> Q[i][0] >> Q[i][1];
Q[i][0]++; Q[i][1]++;
}
}
namespace sub1 {
bool checksub() {
return max(n, q) <= 5000;
}
set <int> G[5005];
bool vis[5005];
void dfs(int u, int p) {
if (vis[u]) return;
vis[u] = 1;
for(auto v : G[u]) if (v != p && vis[v] == 0) {
dfs(v, u);
}
}
vector <int> solve() {
vector <int> res;
FOR(_q, 1, q) {
FOR(i, 1, n) G[i].clear();
int ssc = 0;
FOR(i, 1, Q[_q][0]) {
if (edges[i][0] == 1) {
int u = edges[i][1], v = edges[i][2];
if (u <= Q[_q][1] && v >= Q[_q][1] + 1) continue;
G[u].erase(v);
G[v].erase(u);
} else {
int u = edges[i][1], v = edges[i][2];
if (u <= Q[_q][1] && v >= Q[_q][1] + 1) continue;
G[u].insert(v);
G[v].insert(u);
}
}
FOR(i, 1, n) vis[i] = 0;
FOR(i, 1, n) if (!vis[i]) {
ssc++;
dfs(i, i);
}
res.push_back(ssc);
}
return res;
}
}
struct DisjointSet{
struct Data {
int u, lu, v, lv, ssc;
}; stack <Data> memo;
int ssc, lab[maxN];
int find(int x) {
return lab[x] < 0 ? x : find(lab[x]);
}
bool joint(int u, int v) {
int x = find(u), y = find(v);
if (x == y) return false;
if (lab[x] > lab[y]) swap(x, y);
memo.push({x, lab[x], y, lab[y], ssc});
lab[x]+= lab[y];
lab[y] = x;
ssc--;
return true;
}
int get_version() {
return (int)memo.size();
}
void rollback(int vers) {
while ((int)memo.size() > vers) {
lab[memo.top().u] = memo.top().lu;
lab[memo.top().v] = memo.top().lv;
ssc = memo.top().ssc;
memo.pop();
}
}
} DSU;
namespace sub2 {
bool checksub() {
FOR(i, 1, q) if (Q[i][1] != Q[1][1]) return 0;
return 1;
}
vector <pair <int, int>> st[4 * maxN];
vector <int> ask[maxN];
int ans[maxN], far_query[maxN];
map <pair <int, int>, int> last;
void update(int id, int l, int r, int u, int v, int id_edge) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id].push_back(make_pair(edges[id_edge][1], edges[id_edge][2]));
return;
}
int mid = (l + r) >> 1;
update (id << 1, l, mid, u, v, id_edge);
update (id << 1 | 1, mid + 1, r, u, v, id_edge);
}
void go(int id, int l, int r) {
int vers = DSU.get_version();
for (auto &e : st[id]) DSU.joint(e.first, e.second);
if (l == r) {
for (auto &id : ask[l]) {
ans[id] = DSU.ssc;
}
DSU.rollback(vers);
return;
}
int mid = (l + r) >> 1;
go (id << 1, l, mid);
go (id << 1 | 1, mid + 1, r);
DSU.rollback(vers);
}
vector <int> solve() {
int border = Q[1][1];
FOR(i, 1, m) {
if (edges[i][1] <= border && edges[i][2] > border) continue;
if (edges[i][0] == 0) {
far_query[i] = m;
last[make_pair(edges[i][1], edges[i][2])] = i;
} else {
far_query[last[make_pair(edges[i][1], edges[i][2])]] = i - 1;
}
}
FOR(i, 1, m) if (edges[i][0] == 0) {
update(1, 1, m, i, far_query[i], i);
}
FOR(i, 1, q) ask[Q[i][0]].push_back(i);
FOR(i, 1, n) DSU.lab[i] = - 1;
DSU.ssc = n;
go(1, 1, m);
vector <int> res;
FOR(i, 1, q) res.push_back(ans[i]);
// FOR(i, 1, q) cout << ans[i] << " ";
return res;
}
}
namespace sub3 {
int ans[maxN];
set <pair <int, int>> out_block, in_block;
vector <pair <int, int>> eblock[maxN];
vector <int> ask[maxN], askp[maxN];
vector <int> g[maxN];
void solve() {
FOR(i, 1, q) ask[Q[i][0]].push_back(i);
for (int i = 1; i <= m; i+= 320) {
int L = i, R = min(m, i + 320 - 1);
in_block.clear();
FOR(j, 1, n) askp[j].clear();
FOR(j, L, R) {
int u = edges[j][1], v = edges[j][2];
if (out_block.find(make_pair(u, v)) != out_block.end()) {
out_block.erase(make_pair(u, v));
in_block.insert(make_pair(u, v));
}
for (auto id : ask[j]) askp[Q[id][1]].push_back(id);
}
FOR(j, L, R) {
int u = edges[j][1], v = edges[j][2];
if (edges[j][0] == 0) {
in_block.insert(make_pair(u, v));
} else in_block.erase(make_pair(u, v));
for (auto it : in_block) eblock[j].push_back(it);
}
FOR(j, 1, n) {
DSU.lab[j] = - 1;
g[j].clear();
DSU.ssc = n;
}
while (!DSU.memo.empty()) DSU.memo.pop();
for (auto x : out_block) g[x.se].push_back(x.fi);
FOR(j, 1, n) {
for (auto x : g[j]) DSU.joint(x, j);
int vers = DSU.get_version();
for (auto id : askp[j]) {
for (auto x : eblock[Q[id][0]]) {
if (max(x.first, x.second) <= j) DSU.joint(x.first, x.second);
}
ans[id]+= DSU.ssc;
DSU.rollback(vers);
}
}
FOR(j, 1, n) {
DSU.lab[j] = - 1;
g[j].clear();
DSU.ssc = n;
}
while (!DSU.memo.empty()) DSU.memo.pop();
for (auto x : out_block) g[x.fi].push_back(x.se);
FORD(j, n, 1) {
int vers = DSU.get_version();
for (auto id : askp[j]) {
for (auto x : eblock[Q[id][0]]) {
if (min(x.first, x.second) > j) DSU.joint(x.first, x.second);
}
ans[id]+= DSU.ssc;
DSU.rollback(vers);
}
for (auto x : g[j]) DSU.joint(x, j);
}
for (auto x : in_block) out_block.insert(x);
}
FOR(i, 1, q) cout << ans[i] - n << " ";
}
}
vector <int> simulateCollapse(int N, vector<int> T, vector<int> X, vector<int> Y, vector<int> W, vector<int> P) {
n = N;
m = X.size();
q = W.size();
FOR(i, 0, m - 1) {
edges[i + 1][0] = T[i];
edges[i + 1][1] = X[i] + 1;
edges[i + 1][2] = Y[i] + 1;
if (edges[i + 1][1] > edges[i + 1][2]) swap(edges[i + 1][1], edges[i + 1][2]);
}
for (int i = 0; i < q; i++) {
Q[i + 1][0] = W[i] + 1;
Q[i + 1][1] = P[i] + 1;
}
vector <int> res;
if (sub1::checksub()) res = sub1::solve();
else if (sub2::checksub()) res = sub2::solve();
else res = sub3::solve();
return res;
}
void process() {
vector <int> res;
// if (sub1::checksub()) res = sub1::solve();
// for (int &val : res) cout << val << " ";
// cout << "\n";
// if (sub2::checksub()) res = sub2::solve();
// for (int &val : res) cout << val << " ";
// cout << "\n";
sub3::solve();
}