| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1159935 | Der_Vlapos | Collapse (JOI18_collapse) | C++20 | 0 ms | 0 KiB |
#include "collapse.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define pb push_back
#define all(v) v.begin(), v.end()
struct DSU
{
struct change
{
int x, px, szx, y, py, szy, cnt;
};
stack<change> changes;
vector<int> p, sz;
int cnt = 0;
void init(int n)
{
cnt = n;
p.resize(n);
sz.resize(n);
for (int i = 0; i < n; ++i)
{
sz[i] = 1;
p[i] = i;
}
}
int getR(int v)
{
return p[v] == v ? v : p[v] = getR(p[v]);
}
void undo()
{
assert(changes.size());
auto c = changes.top();
changes.pop();
cnt = c.cnt;
p[c.x] = c.px;
sz[c.x] = c.szx;
p[c.y] = c.py;
sz[c.y] = c.szy;
}
void merge(int a, int b)
{
a = getR(a);
b = getR(b);
changes.push({a, p[a], sz[a], b, p[b], sz[b], cnt});
if (a == b)
return;
cnt--;
if (sz[a] < sz[b])
swap(a, b);
p[b] = a;
sz[a] += sz[b];
}
};
struct segTree
{
struct Node
{
vector<pii> segs;
vector<int> qrs;
};
vector<Node> tree;
DSU dsu;
int sz = 0;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz);
}
void addQr(int pos, int id, int v, int lv, int rv)
{
if (rv - lv == 1)
{
tree[v].qrs.pb(id);
return;
}
int m = (lv + rv) >> 1;
if (pos < m)
addQr(pos, id, v * 2 + 1, lv, m);
else
addQr(pos, id, v * 2 + 2, m, rv);
}
void addQr(int pos, int id)
{
addQr(pos, id, 0, 0, sz);
}
void addSeg(int l, int r, pii e, int v, int lv, int rv)
{
if (l <= lv and rv <= r)
{
tree[v].segs.push_back(e);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
addSeg(l, r, e, v * 2 + 1, lv, m);
addSeg(l, r, e, v * 2 + 2, m, rv);
}
void addSeg(int l, int r, pii e)
{
addSeg(l, r, e, 0, 0, sz);
}
void traverse(vector<int> &ans, int v, int lv, int rv)
{
for (auto e : tree[v].segs)
dsu.merge(e.f, e.s);
// cerr << v << " " << lv << " " << rv << "WAT\n";
if (rv - lv == 1)
{
for (auto id : tree[v].qrs)
ans[id] = dsu.cnt;
}
int m = (lv + rv) >> 1;
if (rv - lv > 1)
{
traverse(ans, v * 2 + 1, lv, m);
traverse(ans, v * 2 + 2, m, rv);
}
for (int i = 0; i < tree[v].segs.size(); ++i)
dsu.undo();
}
void traverse(vector<int> &ans)
{
traverse(ans, 0, 0, sz);
}
};
std::vector<int> simulateCollapse(int n, std::vector<int> t, std::vector<int> x, std::vector<int> y, std::vector<int> w, std::vector<int> p)
{
int q = w.size();
for (int i = 0; i < x.size(); ++i)
if (x[i] > y[i])
swap(x[i], y[i]);
int m = x.size();
int badP = p[0];
vector<pii> qrs;
for (int i = 0; i < q; ++i)
qrs.pb({w[i], i});
sort(all(qrs));
vector<pair<pii, pii>> edges;
int timer = 0;
{
int u = 0;
set<pair<pii, int>> curEdges;
for (int i = 0; i < m; ++i)
if (y[i] <= badP or badP + 1 <= x[i])
{
while (u < q and qrs[u].f < i)
{
qrs[u].f = timer;
}
timer++;
if (t[i] == 0)
curEdges.insert({{x[i], y[i]}, timer});
else
{
auto it = curEdges.lower_bound({{x[i], y[i]}, -1});
edges.pb({{x[i], y[i]}, {it->s, timer}});
curEdges.erase(it);
}
}
for (; u < q; ++u)
qrs[u].f = timer;
timer++;
for (auto [e, st] : curEdges)
edges.pb({e, {st, timer}});
}
segTree tree;
tree.init(timer);
tree.dsu.init(n);
for (auto [t, id] : qrs)
{
tree.addQr(t, id);
}
for (auto [e, t] : edges)
tree.addSeg(t.f, t.s, e);
vector<int> ans(q);
tree.traverse(ans);
return ans;
}
#include "collapse.h"
#include <cstdio>
#include <cstdlib>
int main(int argc, char *argv[])
{
int N, C, Q;
scanf("%d%d%d", &N, &C, &Q);
std::vector<int> T(C), X(C), Y(C);
for (int i = 0; i < C; i++)
{
scanf("%d%d%d", &T[i], &X[i], &Y[i]);
}
std::vector<int> W(Q), P(Q);
for (int i = 0; i < Q; i++)
{
scanf("%d%d", &W[i], &P[i]);
}
auto res = simulateCollapse(N, T, X, Y, W, P);
for (auto i : res)
{
printf("%d\n", i);
}
}