| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 411466 | mhy908 | 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 mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;
const int BUC=300;
struct UNION_FIND{
int par[100010], sz[100010], cnt;
vector<int> vc;
void init(int num){for(int i=1; i<=num; i++)par[i]=i, sz[i]=1; cnt=0;}
int findpar(int num){return num==par[num]?num:findpar(par[num]);}
void mergepar(int a, int b){
a=findpar(a);
b=findpar(b);
if(a==b)return;
if(sz[a]<sz[b])swap(a, b);
vc.eb(b);
par[b]=a;
sz[a]+=sz[b];
cnt++;
}
void rollback(){
int tmp=vc.back();
vc.pop_back();
sz[par[tmp]]-=sz[tmp];
par[tmp]=tmp;
cnt--;
}
}uf;
int n, m, q, query[100010], ans[100010];
pair<int, pii> edge[100010];
vector<int> qlst[100010];
bool cmpl(pii a, pii b){return a.S<b.S;}
bool cmpr(pii a, pii b){return a.F>b.F;}
void solve(int s, int e){
set<pii> edgs;
for(int i=1; i<s; i++){
if(edge[i].F==0)edgs.insert(edge[i].S);
else edgs.erase(edge[i].S);
}
vector<pii> org;
for(int i=s; i<=e; i++){
if(edge[i].F&&edgs.find(edge[i].S)!=edgs.end()){
edgs.erase(edge[i].S);
org.eb(edge[i].S);
}
}
vector<pair<int, pii> > nq;
for(int i=s; i<=e; i++){
for(auto j:qlst[i])nq.eb(query[j], mp(i, j));
}
vector<pii> nedge;
for(auto i:edgs)nedge.eb(i);
sort(all(nedge), cmpl);
sort(all(nq));
uf.init(n);
int pv=0;
for(auto i:nq){
for(; pv<nedge.size(); pv++){
if(nedge[pv].S>i.F)break;
uf.mergepar(nedge[pv].F, nedge[pv].S);
}
set<pii> nadd;
for(auto j:org)nadd.insert(j);
for(int j=s; j<=i.S.F; j++){
if(edge[j].F==0)nadd.insert(edge[j].S);
else nadd.erase(edge[j].S);
}
int nsz=uf.vc.size();
for(auto j:nadd){
if(j.S<=i.F)uf.mergepar(j.F, j.S);
}
ans[i.S.S]+=i.F-uf.cnt;
while(uf.vc.size()>nsz)uf.rollback();
}
sort(all(nedge), cmpr);
reverse(all(nq));
uf.init(n);
pv=0;
for(auto i:nq){
for(; pv<nedge.size(); pv++){
if(nedge[pv].F<=i.F)break;
uf.mergepar(nedge[pv].F, nedge[pv].S);
}
set<pii> nadd;
for(auto j:org)nadd.insert(j);
for(int j=s; j<=i.S.F; j++){
if(edge[j].F==0)nadd.insert(edge[j].S);
else nadd.erase(edge[j].S);
}
int nsz=uf.vc.size();
for(auto j:nadd){
if(j.F>i.F)uf.mergepar(j.F, j.S);
}
ans[i.S.S]+=n-i.F-uf.cnt;
while(uf.vc.size()>nsz)uf.rollback();
}
}
int main(){
scanf("%d %d %d", &n, &m, &q);
for(int i=1; i<=m; i++){
scanf("%d %d %d", &edge[i].F, &edge[i].S.F, &edge[i].S.S);
if(edge[i].S.F>edge[i].S.S)swap(edge[i].S.F, edge[i].S.S);
edge[i].S.F++, edge[i].S.S++;
}
for(int i=1; i<=q; i++){
int a, b;
scanf("%d %d", &a, &b);
qlst[a+1].eb(i);
query[i]=b+1;
}
for(int i=1; i<=m; i+=BUC)solve(i, min(m, i+BUC-1));
for(int i=1; i<=q; i++)printf("%d\n", ans[i]);
}