Submission #889105

#	Time	Username	Problem	Language	Result	Execution time	Memory
889105		BBart888	Bridges (APIO19_bridges)	C++14	100 / 100	1542 ms	72480 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

const int MAXN= 1e6 + 111;

using  ll = long long;

int sz[MAXN];
int par[MAXN];
stack<int> stk;
const int B = 1000;
int n;
void reset()
{
	for(int i =1;i<=n;i++)
	{	par[i] = i;
		sz[i] =1;
	
}
}


int find(int a)
{
	while(par[a] != a)
		a = par[a];
	return a;
}


void onion(int a,int b)
{
	a = find(a);
	b = find(b);
	
	if(a == b)
		return;
	if(sz[a] > sz[b])	
		swap(a,b);
	sz[b]+=sz[a];
	par[a] = par[b];
	stk.push(a);
}


void roll_back(int x)
{
	while((int)stk.size() > x)
	{
		int k =stk.top();
		stk.pop();
		sz[find(k)] -= sz[k];
		par[k] = k;
	}
}

int m;
int u[MAXN];
int v[MAXN];
int w[MAXN];
int t[MAXN];
int x[MAXN];
int y[MAXN];
bool changed[MAXN];
vector<int> to_join[MAXN];
int ans[MAXN];
int q;


int main()
{
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	
	for(int i =1;i<=m;i++)
		cin>>u[i]>>v[i]>>w[i];
	
	cin>>q;
	
	for(int i =1;i<=q;i++)
		cin>>t[i]>>x[i]>>y[i];
		
	for(int l =1;l<=q;l+=B)
	{
		int r = min(l+B-1,q);
		reset();
		
		fill(changed+1,changed+m+1,false);

		vector<int> ask,upd,unchanged;
		
		for(int i = l;i<=r;i++)
		{
			if(t[i] == 1)
			{
				changed[x[i]] = true;
				upd.push_back(i);
			}
			else
				ask.push_back(i);
		}
		
		for(int i =1;i<=m;i++)
			if(!changed[i])
				unchanged.push_back(i);
		
		for(int i = l;i<=r;i++)
		{
			if(t[i] == 1)
				w[x[i]] = y[i];
			else
			{
				to_join[i-l].clear();
				for(int j : upd)
					if(w[x[j]] >= y[i])
						to_join[i-l].push_back(x[j]);
			}
		}
		
		sort(ask.begin(),ask.end(),[&](int a,int b){return y[a] > y[b];});
		sort(unchanged.begin(),unchanged.end(),[&](int a,int b){return w[a] > w[b];});
		
		int ptr =0;
		
		for(int i : ask)
		{
			while(ptr < (int)unchanged.size() && y[i] <= w[unchanged[ptr]])
				{
					
					onion(u[unchanged[ptr]],v[unchanged[ptr]]);
					ptr++;
				}
			
			int prv_size = stk.size();
			for(int j : to_join[i-l])
				onion(u[j],v[j]);
			//cout<<find(x[i])<<" "<<'\n';
			ans[i]= sz[find(x[i])];
			//cout<<"ge\n";	
			roll_back(prv_size);
		}
	}

	

	for(int i = 1;i<=q;i++)
		if(t[i] == 2)
			cout<<ans[i]<<"\n";
	
	
	
	return 0;
}

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