| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 425024 | CodePlatina | Collapse (JOI18_collapse) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <map>
#include <set>
#include <cstdlib>
#include <unordered_set>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
const int INF = (int)1e9 + 7;
const int Q = 600;
using namespace std;
vector<pii> eg;
vector<pii> lf;
map<pii, int> M;
vector<int> lsu[101010];
vector<int> lsd[101010];
vector<pii> qr[101010];
struct UF
{
int par[101010];
short rnk[101010];
int pnt;
int cnt, __cnt;
vector<pii> rec;
UF(void) : pnt(0), cnt(0), __cnt(0), rec() { for(int i = 0; i < 101010; ++i) par[i] = i, rnk[i] = 0; }
int fnd(int x) { return x == par[x] ? x : fnd(par[x]); }
void uni(int x, int y)
{
x = fnd(x), y = fnd(y);
if(x == y) return;
if(rnk[x] == rnk[y])
{
rec.push_back({0, x});
rec.push_back({1, y});
++rnk[x];
par[y] = x;
}
else if(rnk[x] > rnk[y])
{
rec.push_back({1, y});
par[y] = x;
}
else
{
rec.push_back({1, x});
par[x] = y;
}
++cnt;
}
void save(void) { pnt = (int)rec.size(); __cnt = cnt; }
void rollback(void)
{
while((int)rec.size() > pnt)
{
auto [c, x] = rec.back();
if(c == 0) --rnk[x];
else par[x] = x;
rec.pop_back();
}
cnt = __cnt;
}
}uf[200];
vector<int> ind[200];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, T; cin >> n >> m >> T;
for(int i = 0; i < m; ++i)
{
int c, x, y; cin >> c >> x >> y;
if(x > y) swap(x, y);
if(c == 0)
{
M[{x, y}] = (int)eg.size();
eg.push_back({x, y});
lf.push_back({i, m});
}
else
{
lf[M[{x, y}]].ss = i;
M.erase({x, y});
}
}
for(int i = 0; i < (int)eg.size(); ++i)
{
if(eg[i].ff > 0) lsd[eg[i].ff - 1].push_back(i);
lsu[eg[i].ss].push_back(i);
}
for(int i = 0; i < T; ++i)
{
int x, y; cin >> x >> y;
qr[y].push_back({x, i});
}
vector<int> ans(T); for(auto &i : ans) i = n;
for(int i = 0; i < n; ++i)
{
for(int k = 0; k < (int)lsu[i].size(); ++k)
{
auto [x, y] = eg[lsu[i][k]];
auto [s, e] = lf[lsu[i][k]];
for(int j = s / Q; j <= (e - 1) / Q; ++j)
{
int l = j * Q, r = l + Q;
if(s <= l && r <= e) uf[j].uni(x, y);
else ind[j].push_back(lsu[i][k]);
}
}
for(auto [t, q] : qr[i])
{
int j = t / Q;
uf[j].save();
for(int k = 0; k < (int)ind[j].size(); ++k)
{
auto [x, y] = eg[ind[j][k]];
auto [s, e] = lf[ind[j][k]];
if(s <= t && t < e) uf[j].uni(x, y);
}
ans[q] -= uf[j].cnt;
uf[j].rollback();
}
}
for(int i = 0; i <= m / Q; ++i)
{
uf[i].pnt = uf[i].cnt = uf[i].__cnt = 0;
uf[i].rollback();
ind[i].clear();
ind[i].shrink_to_fit();
}
for(int i = n - 1; i >= 0; --i)
{
for(int k = 0; k < (int)lsd[i].size(); ++k)
{
auto [x, y] = eg[lsd[i][k]];
auto [s, e] = lf[lsd[i][k]];
for(int j = s / Q; j <= (e - 1) / Q; ++j)
{
int l = j * Q, r = l + Q;
if(s <= l && r <= e) uf[j].uni(x, y);
else ind[j].push_back(lsd[i][k]);
}
}
for(auto [t, q] : qr[i])
{
int j = t / Q;
uf[j].save();
for(int k = 0; k < (int)ind[j].size(); ++k)
{
auto [x, y] = eg[ind[j][k]];
auto [s, e] = lf[ind[j][k]];
if(s <= t && t < e) uf[j].uni(x, y);
}
ans[q] -= uf[j].cnt;
uf[j].rollback();
}
}
for(int i = 0; i < T; ++i) cout << ans[i] << '\n';
}