| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 422861 | songc | Collapse (JOI18_collapse) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, M, Q, B=500, cnt;
int P[101010], ans[101010];
vector<pii> RB;
int rt(int u){
if (P[u]<0) return u;
return rt(P[u]);
}
void uni(int u, int v){
u = rt(u), v = rt(v);
if (u == v) return;
if (P[u] > P[v]) swap(u, v);
RB.pb(pii(u, P[u]));
RB.pb(pii(v, P[v]));
P[u] += P[v], P[v] = u;
RB.pb(pii(-1,0)), cnt--;
}
struct Event{int t, x, u, v;} E[202020];
vector<pii> O;
vector<Event> BE, QR;
map<pii,int> S;
int main(){
scanf("%d %d %d", &N, &M, &Q);
for (int i=0; i<M; i++){
scanf("%d %d %d", &E[i].t, &E[i].u, &E[i].v), E[i].x = i;
if (E[i].u > E[i].v) swap(E[i].u, E[i].v);
}
for (int i=M; i<M+Q; i++) scanf("%d %d", &E[i].x, &E[i].u), E[i].t = 2, E[i].v = i-M;
M += Q;
sort(E, E+M, [&](Event a, Event b){
if (a.x != b.x) return a.x < b.x;
return a.t < b.t;
});
for (int i=0; i*B<M; i++){
S.clear(), O.clear(), BE.clear(), QR.clear();
for (int j=0; j<(i+1)*B && j<M; j++){
if (E[j].t == 0) S[pii(E[j].u,E[j].v)] = E[j].x;
if (E[j].t == 1){
if (j >= i*B) BE.pb((Event){S[pii(E[j].u,E[j].v)], E[j].x-1, E[j].u, E[j].v});
S[pii(E[j].u,E[j].v)] = -1;
}
if (E[j].t == 2 && j>=i*B) QR.pb(E[j]);
}
for (auto it : S){
if (it.se < 0) continue;
if (it.se <= E[i*B].x) O.pb(it.fi);
else BE.pb((Event){it.se, M, it.fi.fi, it.fi.se});
}
sort(QR.begin(), QR.end(), [&](Event a, Event b){return a.u < b.u;});
sort(O.begin(), O.end(), [&](pii a, pii b){return a.se < b.se;});
int p=0;
cnt=0;
for (int j=0; j<N; j++) P[j] = -1;
RB.clear();
for (Event q : QR){
while (p < O.size() && O[p].se <= q.u) uni(O[p].fi, O[p].se), p++;
int rb = RB.size();
for (Event e : BE) if (e.t <= q.x && q.x <= e.x && e.v <= q.u) uni(e.u, e.v);
ans[q.v] = cnt;
while (RB.size() > rb){
pii t = RB.back(); RB.pop_back();
if (t.fi < 0) cnt++;
else P[t.fi] = t.se;
}
}
sort(QR.begin(), QR.end(), [&](Event a, Event b){return a.u > b.u;});
sort(O.begin(), O.end(), [&](pii a, pii b){return a.fi > b.fi;});
p=0, cnt=0;
for (int j=0; j<N; j++) P[j] = -1;
RB.clear();
for (Event q : QR){
while (p < O.size() && O[p].fi > q.u) uni(O[p].fi, O[p].se), p++;
int rb = RB.size();
for (Event e : BE) if (e.t <= q.x && q.x <= e.x && e.u > q.u) uni(e.u, e.v);
ans[q.v] += cnt;
while (RB.size() > rb){
pii t = RB.back(); RB.pop_back();
if (t.fi < 0) cnt++;
else P[t.fi] = t.se;
}
}
}
for (int i=0; i<Q; i++) printf("%d\n", N+ans[i]);
return 0;
}