제출 #1219378

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219378		boclobanchat	다리 (APIO19_bridges)	C++20	100 / 100	2125 ms	7096 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
struct edge { int l,r,v; };
struct query { int t,idx,v; };
const int MAXN=1e5+5;
const int sqr=600;
int dsu[MAXN],cnt[MAXN],ans[MAXN],len[MAXN],idx[MAXN],pre[MAXN],o[MAXN];
edge E[MAXN],e2[MAXN];
query Q[MAXN];
bool ck[MAXN];
stack< pair<int,int> > st;
bool comp(edge a,edge b) { return a.v>b.v; }
bool comp2(int a,int b) { return Q[a].v>Q[b].v; }
int root(int i)
{
	if(!dsu[i]) return i;
	return root(dsu[i]);
}
void merge(int i,int j)
{
	if((i=root(i))==(j=root(j)))
	{
		st.push({-1,-1});
		return ;
	}
	if(cnt[i]<cnt[j]) swap(i,j);
	dsu[j]=i,cnt[i]+=cnt[j],st.push({i,j});
}
void rollback()
{
	pair<int,int> a=st.top();
	st.pop();
	if(a.first<0) return ;
	dsu[a.second]=0,cnt[a.first]-=cnt[a.second];
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m,q;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
    	int l,r,v;
    	cin>>l>>r>>v;
    	E[i]={l,r,v};
	}
	for(int i=1;i<=n;i++) cnt[i]=1;
	cin>>q;
	int preq=1;
	for(int i=1;i<=q;i++)
	{
		idx[i]=i;
		cin>>Q[i].t>>Q[i].idx>>Q[i].v;
		if(i==q||i%sqr==0)
		{
			int cnt1=0,r=1,cnt2=0;
			for(int j=preq;j<=i;j++) if(Q[j].t==1) ck[Q[j].idx]=true;
			for(int j=1;j<=m;j++) if(!ck[j]) e2[++cnt1]=E[j];
			else o[++cnt2]=j,len[j]=E[j].v;
			sort(e2+1,e2+cnt1+1,comp);
			sort(idx+preq,idx+i+1,comp2);
			for(int j=preq;j<=i;j++)
			{
				int p=idx[j];
				if(Q[p].t==2)
				{
					while(r<=cnt1&&e2[r].v>=Q[p].v) merge(e2[r].l,e2[r].r),r++;
					for(int k=1;k<=cnt2;k++) pre[o[k]]=len[o[k]];
					for(int k=preq;k<p;k++) if(Q[k].t==1) len[Q[k].idx]=Q[k].v;
					for(int k=1;k<=cnt2;k++) if(len[o[k]]>=Q[p].v) merge(E[o[k]].l,E[o[k]].r);
					ans[p]=cnt[root(Q[p].idx)];
					for(int k=1;k<=cnt2;k++) 
					{
						if(len[o[k]]>=Q[p].v) rollback();
						len[o[k]]=pre[o[k]];
					}
				}
			}
			for(int j=preq;j<=i;j++) if(Q[j].t==1) ck[Q[j].idx]=false,E[Q[j].idx].v=Q[j].v;
			else cout<<ans[j]<<"\n";
			while(!st.empty()) rollback();
			preq=i+1;
		}
	}
}

• Subtask 1: 13 / 13
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 14 / 14
• Subtask 5: 13 / 13
• Subtask 6: 27 / 27