Submission #124531

#	Time	Username	Problem	Language	Result	Execution time	Memory
124531		TadijaSebez	Bridges (APIO19_bridges)	C++11	100 / 100	2748 ms	49156 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=100050;
const int B=1050;
int w[N],u[N],v[N];
bool ban[N];
int t[N],b[N],c[N];
vector<int> use[B];
struct DSU
{
	int p[N],sz[N];
	void init(){ for(int i=0;i<N;i++) p[i]=i,sz[i]=1;}
	void init(int n){ for(int i=1;i<=n;i++) p[i]=i,sz[i]=1;}
	DSU(){ init();}
	int Find(int u){ return u==p[u]?u:Find(p[u]);}
	stack<int> was;
	void Union(int u, int v)
	{
		u=Find(u);
		v=Find(v);
		if(u==v){ was.push(0);return;}
		if(sz[u]>sz[v])
		{
			p[v]=u;
			sz[u]+=sz[v];
			was.push(v);
		}
		else
		{
			p[u]=v;
			sz[v]+=sz[u];
			was.push(u);
		}
	}
	void Undo()
	{
		int u=was.top();
		was.pop();
		if(u)
		{
			sz[p[u]]-=sz[u];
			p[u]=u;
		}
	}
	int Get(int u){ return sz[Find(u)];}
} DS;
int ans[N];
int main()
{
	int n,m,q;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++) scanf("%i %i %i",&u[i],&v[i],&w[i]);
	scanf("%i",&q);
	for(int i=0;i<q;i++) scanf("%i %i %i",&t[i],&b[i],&c[i]);
	for(int l=0;l<q;l+=B)
	{
		DS.init(n);
		int r=min(q,l+B)-1;
		for(int i=1;i<=m;i++) ban[i]=0;
		vector<int> bn,id;
		for(int i=l;i<=r;i++) if(t[i]==1) ban[b[i]]=1;
		for(int i=1;i<=m;i++)
		{
			if(ban[i]) bn.pb(i);
			else id.pb(i);
		}
		sort(id.begin(),id.end(),[&](int i, int j){ return w[i]>w[j];});
		for(int i=l;i<=r;i++) use[i-l].clear();
		vector<int> qs;
		for(int i=l;i<=r;i++)
		{
			if(t[i]==1) w[b[i]]=c[i];
			else
			{
				for(int j=0;j<bn.size();j++) if(w[bn[j]]>=c[i]) use[i-l].pb(bn[j]);
				qs.pb(i);
			}
		}
		sort(qs.begin(),qs.end(),[&](int i, int j){ return c[i]>c[j];});
		for(int i=0,j=0;i<qs.size();i++)
		{
			while(j<id.size() && w[id[j]]>=c[qs[i]])
			{
				DS.Union(u[id[j]],v[id[j]]);
				j++;
			}
			for(int k=0;k<use[qs[i]-l].size();k++)
			{
				int e=use[qs[i]-l][k];
				DS.Union(u[e],v[e]);
			}
			ans[qs[i]]=DS.Get(b[qs[i]]);
			for(int k=0;k<use[qs[i]-l].size();k++) DS.Undo();
		}
	}
	for(int i=0;i<q;i++) if(t[i]==2) printf("%i\n",ans[i]);
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:76:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j=0;j<bn.size();j++) if(w[bn[j]]>=c[i]) use[i-l].pb(bn[j]);
                 ~^~~~~~~~~~
bridges.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0,j=0;i<qs.size();i++)
                   ~^~~~~~~~~~
bridges.cpp:83:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(j<id.size() && w[id[j]]>=c[qs[i]])
          ~^~~~~~~~~~
bridges.cpp:88:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<use[qs[i]-l].size();k++)
                ~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:94:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<use[qs[i]-l].size();k++) DS.Undo();
                ~^~~~~~~~~~~~~~~~~~~~
bridges.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
bridges.cpp:53:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i",&u[i],&v[i],&w[i]);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i",&q);
  ~~~~~^~~~~~~~~
bridges.cpp:55:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0;i<q;i++) scanf("%i %i %i",&t[i],&b[i],&c[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