| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 368734 | kig9981 | Collapse (JOI18_collapse) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
const int BC=300, SZ=1<<17;
vector<int> adj[100000], BB, tree[2*SZ];
vector<tuple<int,int,int>> qry;
vector<pair<int,int>> E;
map<pair<int,int>,int> idx;
int N, ans[100000], B[100000], LL[100000], color[100000], cnt[100000];
bool EX[100000];
void add_edge(int s, int e, int v)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) tree[s++].push_back(v);
if(~e&1) tree[e--].push_back(v);
}
}
void flip_edge(int c, int i)
{
if(EX[c]) add_edge(LL[c],i-1,c);
else LL[c]=i;
EX[c]^=1;
}
int find_(int a)
{
while(color[a]!=a) a=color[a];
return a;
}
void union_(int a, int b)
{
a=find_(a); b=find_(b);
if(a==b) return;
if(cnt[a]<cnt[b]) swap(a,b);
cnt[color[b]=a]+=cnt[b];
BB.push_back(b);
}
void restore(int sz)
{
while(BB.size()>sz) {
cnt[color[BB.back()]]-=cnt[BB.back()];
color[BB.back()]=color[BB.back()];
BB.pop_back();
}
}
void solve(int bit, int s, int e)
{
int m=(s+e)>>1, bsz=BB.size();
if(qry.size()<=s) return;
for(auto e: tree[bit]) union_(E[e].first,E[e].second);
if(s==e) {
ans[get<2>(qry[m])]=N-BB.size();
restore(bsz);
return;
}
solve(2*bit,s,m);
solve(2*bit+1,m+1,e);
restore(bsz);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int C, Q, w, p;
cin>>N>>C>>Q;
for(int i=0;i<C;i++) {
int t, a, b;
cin>>t>>a>>b;
if(a>b) swap(a,b);
if(idx.count({a,b})==0) {
idx[{a,b}]=E.size();
E.emplace_back(a,b);
}
B[i]=idx[{a,b}];
adj[a].push_back(i);
adj[b].push_back(i);
}
for(int i=0;i<Q;i++) {
int w, p;
cin>>w>>p;
qry.emplace_back(w,p,i);
}
sort(qry.begin(),qry.end(),[&](tuple<int,int,int> a, tuple<int,int,int> b) {
if(get<0>(a)/BC!=get<0>(b)/BC) return get<0>(a)/BC<get<0>(b)/BC;
return get<1>(a)<get<1>(b);
});
memset(LL,w=p=-1,sizeof(LL));
for(int i=0;i<Q;i++) {
auto[cw,cp,j]=qry[i];
while(w<cw) {
int c=B[++w];
auto[a,b]=E[c];
if(a<=p && p<b) continue;
flip_edge(c,i);
}
while(w>cw) {
int c=B[w--];
auto[a,b]=E[c];
if(a<=p && p<b) continue;
flip_edge(c,i);
}
while(p<cp) {
int c=++p;
for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
}
while(p>cp) {
int c=p--;
for(auto t: adj[c]) if(t<=w) flip_edge(B[t],i);
}
}
for(int i=0;i<E.size();i++) if(EX[i]) add_edge(LL[i],Q-1,i);
for(int i=0;i<N;i++) cnt[color[i]=i]=1;
solve(1,0,SZ-1);
for(int i=0;i<Q;i++) cout<<ans[i]<<'\n';
return 0;
}