Submission #743673

#	Time	Username	Problem	Language	Result	Execution time	Memory
743673		Azther0z	Bridges (APIO19_bridges)	C++11	100 / 100	2231 ms	32128 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
const int MX=100000;
const int BLOCK=1000;
int n,m,q;
int A[MX+1],B[MX+1],W[MX+1];
int op[MX+1],X[MX+1],Y[MX+1];
int dsu[MX+1],sz[MX+1],result[MX+1];
stack<int> stk;
vector<vector<int>> toMerge(BLOCK+1);
bitset<MX+1> changed;
int find(int x)
{
	while(x!=dsu[x])
		x=dsu[x];
	return x;
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y) return;
	if(sz[x]<sz[y]) swap(x,y);
	sz[x]+=sz[y];
	dsu[y]=x;
	stk.push(y);
}
void rollback(int x)
{
	while(stk.size()>x)
	{
		sz[dsu[stk.top()]]-=sz[stk.top()];
		dsu[stk.top()]=stk.top();
		stk.pop();
	}
}
void reset()
{
	for(int i=1;i<=n;i++)
	{
		dsu[i]=i;
		sz[i]=1;
	}
	changed=0;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&A[i],&B[i],&W[i]);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
		scanf("%d%d%d",&op[i],&X[i],&Y[i]);
	for(int l=1;l<=q;l+=BLOCK)
	{
		int r=min(q+1,l+BLOCK);
		reset();
		vector<int> calc,update,unchanged;
		for(int i=l;i<r;i++)
		{
			if(op[i]==1)
			{
				changed[X[i]]=true;
				update.push_back(i);
			}
			else
			{
				calc.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(op[i]==1)
			{
				W[X[i]]=Y[i];
			}
			else
			{
				toMerge[i-l].clear();
				for(auto j:update)
					if(W[X[j]]>=Y[i])
						toMerge[i-l].push_back(X[j]);
			}
		}
		sort(calc.begin(),calc.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 idx=0;
		for(auto i:calc)
		{
			while(idx<unchanged.size()&&W[unchanged[idx]]>=Y[i])
			{
				merge(A[unchanged[idx]],B[unchanged[idx]]);
				idx++;
			}
			int prev=stk.size();
			for(auto j:toMerge[i-l])
				merge(A[j],B[j]);
			result[i]=sz[find(X[i])];
			rollback(prev);
		}
	}
	for(int i=1;i<=q;i++)
		if(op[i]==2)
			printf("%d\n",result[i]);
}

Compilation message (stderr)

bridges.cpp: In function 'void rollback(int)':
bridges.cpp:29:18: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |  while(stk.size()>x)
      |        ~~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:91:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |    while(idx<unchanged.size()&&W[unchanged[idx]]>=Y[i])
      |          ~~~^~~~~~~~~~~~~~~~~
bridges.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
bridges.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d%d%d",&A[i],&B[i],&W[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
bridges.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d%d%d",&op[i],&X[i],&Y[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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