Submission #340884

#	Time	Username	Problem	Language	Result	Execution time	Memory
340884		ogibogi2004	Bridges (APIO19_bridges)	C++14	46 / 100	3079 ms	187680 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+6;
const int MAXM=1e5+6;
const int SQRT=666;
int n,m,q;
int ans[MAXM];
struct edge
{
	int u,v,w;
	bool operator<(edge const& other)const
	{
		return w<other.w;
	}
};
struct query
{
	int type;
	int a,b;
	bool operator<(query const& other)const
	{
		return b<other.b;
	}
};
struct query1
{
	int time;
	int s,w;
	bool operator<(query1 const& other)const
	{
		return w<other.w;
	}
};
edge e[MAXM];
vector<query>blocks[SQRT];
bool used[MAXM];
bool changed[MAXM];
int par[MAXN],rnk[MAXN],sz[MAXN];
struct save
{
	int u,v,rnku,rnkv,szu,szv;
};
stack<save>lol;
int getRoot(int u)
{
	if(u==par[u])return u;
	return getRoot(par[u]);
}
void join(int u,int v)
{
	lol.push({u,v,rnk[u],rnk[v],sz[u],sz[v]});
	if(rnk[u]>rnk[v])
	{
		par[v]=u;
		sz[u]+=sz[v];
	}
	else if(rnk[v]>rnk[u])
	{
		par[u]=v;
		sz[v]+=sz[u];
	}
	else
	{
		par[v]=u;
		++rnk[v];
		sz[u]+=sz[v];
	}
}
void rollback()
{
	save xd=lol.top();lol.pop();
	par[xd.u]=xd.u;
	par[xd.v]=xd.v;
	sz[xd.u]=xd.szu;
	sz[xd.v]=xd.szv;
	rnk[xd.u]=xd.rnku;
	rnk[xd.v]=xd.rnkv;
}
void add_edge(edge o)
{
	int u=getRoot(o.u);
	int v=getRoot(o.v);
	if(u!=v)join(u,v);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m;
	int cb=-1;
	for(int i=0;i<m;++i)
	{
		cin>>e[i].u>>e[i].v>>e[i].w;
		e[i].w=-e[i].w;
	}
	cin>>q;
	for(int i=0;i<q;++i)
	{
		if(cb==-1||blocks[cb].size()==SQRT)cb++;
		int t;
		cin>>t;
		if(t==1)
		{
			int b,r;
			cin>>b>>r;
			--b;
			blocks[cb].push_back({t,b,-r});
		}
		if(t==2)
		{
			int w,s;
			cin>>s>>w;
			blocks[cb].push_back({t,s,-w});
		}
		ans[i]=-1;
	}
	int s=0;
	vector<edge>unchanged;vector<query1>a;vector<int>used_edges;
	for(int i=0;i<=cb;++i)
	{
		int sz1=blocks[i].size();
		for(auto ivan:blocks[i])
		{
			if(ivan.type==1)changed[ivan.a]=1;
		}
		unchanged.clear();
		for(int j=0;j<m;++j)
		{
			if(!changed[j])unchanged.push_back(e[j]);
		}
		sort(unchanged.begin(),unchanged.end());
		for(int j=1;j<=n;++j)
		{
			par[j]=j;sz[j]=1;
			rnk[j]=1;
		}
		a.clear();
		for(int j=0;j<sz1;++j)
		{
			if(blocks[i][j].type==2)
			{
				a.push_back({j+s,blocks[i][j].a,blocks[i][j].b});
			}
		}
		sort(a.begin(),a.end());
		used_edges.clear();
		int pp=0;
		for(int j=0;j<a.size();++j)
		{
			used_edges.clear();
			while(pp<unchanged.size()&&unchanged[pp].w<=a[j].w)
			{
				add_edge(unchanged[pp]);++pp;
			}
			for(int l=a[j].time-s;l>=0;--l)
			{
				if(blocks[i][l].type==1)
				{
					if(used[blocks[i][l].a])
					{
						used[blocks[i][l].a]=1;
						continue;
					}
					if(blocks[i][l].b>a[j].w)
					{
						used[blocks[i][l].a]=1;
						continue;
					}
					int idx=blocks[i][l].a;
					int n1=getRoot(e[idx].u);
					int n2=getRoot(e[idx].v);
					if(n1!=n2)
					{
						join(n1,n2);
						used_edges.push_back(idx);
					}
					used[blocks[i][l].a]=1;
				}
			}
			for(int l=a[j].time-s;l<sz1;++l)
			{
				if(blocks[i][l].type==2)continue;
				if(used[blocks[i][l].a])
				{
					continue;
				}
				int idx=blocks[i][l].a;
				if(e[idx].w>a[j].w)
				{
					used[idx]=1;
					continue;
				}
				int n1=getRoot(e[idx].u);
				
				int n2=getRoot(e[idx].v);
				if(n1!=n2)
				{
					join(n1,n2);
					used_edges.push_back(idx);
				}
				used[idx]=1;
			}
			ans[a[j].time]=sz[getRoot(a[j].s)];
			for(int l=used_edges.size()-1;l>=0;--l)
			{
				rollback();
			}
			for(int l=sz1-1;l>=0;--l)
			{
				
				if(blocks[i][l].type==1)
				{
					used[blocks[i][l].a]=0;
				}
			}
		}
		for(int j=0;j<sz1;++j)
		{
			if(blocks[i][j].type==1)
			{
				e[blocks[i][j].a].w=blocks[i][j].b;
				changed[blocks[i][j].a]=0;
			}
		}
		s+=sz1;
	}
	for(int i=0;i<q;++i)
	{
		if(ans[i]!=-1)cout<<ans[i]<<'\n';
	}
return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:149:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for(int j=0;j<a.size();++j)
      |               ~^~~~~~~~~
bridges.cpp:152:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |    while(pp<unchanged.size()&&unchanged[pp].w<=a[j].w)
      |          ~~^~~~~~~~~~~~~~~~~

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