Submission #340846

#	Time	Username	Problem	Language	Result	Execution time	Memory
340846		ogibogi2004	Bridges (APIO19_bridges)	C++14	46 / 100	3084 ms	309976 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+6;
const int MAXM=1e5+6;
const int SQRT=400;
int n,m,q;
int ans[MAXM];
struct edge
{
	int u,v,w;
	bool operator<(edge const& other)const
	{
		if(w!=other.w)return w<other.w;
		return v<other.v;
	}
};
struct query
{
	int type;
	int a,b;
	bool operator<(query const& other)const
	{
		if(b!=other.b)return b<other.b;
		return type<other.type;
	}
};
struct query1
{
	int time;
	int s,w;
	bool operator<(query1 const& other)const
	{
		return w<other.w;
	}
};
vector<edge>e;
vector<vector<query> >blocks;
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()
{
	//if(lol.size()==0)return;
	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)
{
	//cout<<"*"<<o.u<<" "<<o.v<<endl;
	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;
	for(int i=0;i<m;++i)
	{
		int x,y,z;
		cin>>x>>y>>z;
		e.push_back({x,y,-z});
	}
	cin>>q;
	for(int i=0;i<q;++i)
	{
		if(blocks.size()==0||blocks.back().size()==SQRT)blocks.emplace_back();
		int t;
		cin>>t;
		if(t==1)
		{
			int b,r;
			cin>>b>>r;
			b--;
			blocks.back().push_back({t,b,-r});
		}
		if(t==2)
		{
			int w,s;
			cin>>s>>w;
			blocks.back().push_back({t,s,-w});
		}
	}
	memset(ans,-1,sizeof(ans));
	int s=0;
	vector<edge>unchanged;vector<query1>a;vector<int>used_edges;
	for(int i=0;i<blocks.size();++i)
	{
		for(auto ivan:blocks[i])
		{
			if(ivan.type==1)changed[ivan.a]=1;
		}
		unchanged.clear();
		for(int j=0;j<e.size();++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<blocks[i].size();++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)
		{
			//cout<<")("<<a[j].time<<" "<<a[j].s<<" "<<a[j].w<<endl;
			used_edges.clear();
			while(pp<unchanged.size()&&unchanged[pp].w<=a[j].w)
			{
				add_edge(unchanged[pp]);++pp;
			}
			//memset(used,0,sizeof(used));
			for(int l=a[j].time-s;l>=0;--l)
			{
				if(blocks[i][l].type==1)
				{
					//cout<<"+"<<blocks[i][l].a<<" "<<l<<endl;
					if(used[blocks[i][l].a])
					{
						used[blocks[i][l].a]=1;
						continue;
					}
					if(blocks[i][l].b>a[j].w)
					{
						//cout<<"of "<<e[blocks[i][l].a].u<<" "<<e[blocks[i][l].a].v<<endl;
						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)
					{
						//cout<<"**"<<e[idx].u<<"-"<<e[idx].v<<endl;
						join(n1,n2);
						used_edges.push_back(idx);
					}
					used[blocks[i][l].a]=1;
				}
			}
			for(int l=a[j].time-s;l<blocks[i].size();++l)
			{
				if(blocks[i][l].type==2)continue;
				if(used[blocks[i][l].a])
				{
					continue;
				}
				int idx=blocks[i][l].a;
				//cout<<"+"<<idx<<" "<<l<<"\n";
				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)
				{
					//cout<<"***"<<e[idx].u<<" "<<e[idx].v<<endl;
					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=blocks[i].size()-1;l>=0;--l)
			{
				
				if(blocks[i][l].type==1)
				{
					//cout<<"-"<<blocks[i][l].a<<" "<<l<<endl;
					used[blocks[i][l].a]=0;
				}
			}
			/*for(int l=0;l<20;l++)
			{
				if(used[l]==1)cout<<"OMG "<<l<<endl;
			}*/
		}
		for(int j=0;j<blocks[i].size();++j)
		{
			if(blocks[i][j].type==1)
			{
				e[blocks[i][j].a].w=blocks[i][j].b;
				changed[blocks[i][j].a]=0;
			}
		}
		s+=blocks[i].size();
	}
	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:124:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<query> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=0;i<blocks.size();++i)
      |              ~^~~~~~~~~~~~~~
bridges.cpp:131:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |   for(int j=0;j<e.size();++j)
      |               ~^~~~~~~~~
bridges.cpp:142:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |   for(int j=0;j<blocks[i].size();++j)
      |               ~^~~~~~~~~~~~~~~~~
bridges.cpp:152:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |   for(int j=0;j<a.size();++j)
      |               ~^~~~~~~~~
bridges.cpp:156:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |    while(pp<unchanged.size()&&unchanged[pp].w<=a[j].w)
      |          ~~^~~~~~~~~~~~~~~~~
bridges.cpp:189:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  189 |    for(int l=a[j].time-s;l<blocks[i].size();++l)
      |                          ~^~~~~~~~~~~~~~~~~
bridges.cpp:233:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  233 |   for(int j=0;j<blocks[i].size();++j)
      |               ~^~~~~~~~~~~~~~~~~

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