제출 #340925

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
340925		ogibogi2004	다리 (APIO19_bridges)	C++14	46 / 100	3092 ms	5356 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e4+6;
const int MAXM=1e5+6;
const int SQRT=800;
int n,m,q;
int ans[MAXM];
struct edge
{
	int u,v,w;
	edge(int _u,int _v,int _w)
	{
		u=_u;
		v=_v;
		w=_w;
	}
	edge()
	{
		
	}
	bool operator<(edge const& other)const
	{
		return w<other.w;
	}
}e[MAXM];
struct query
{
	int type;
	int a,b;
	query(int _type,int _a,int _b)
	{
		type=_type;
		a=_a;
		b=_b;
	}
	bool operator<(query const& other)const
	{
		return b<other.b;
	}
};
struct query1
{
	int time;
	int s,w;
	query1(int _time,int _s,int _w)
	{
		time=_time;
		s=_s;
		w=_w;
	}
	bool operator<(query1 const& other)const
	{
		return w<other.w;
	}
};
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;
	save(){}
	save(int _u,int _v,int _rnku,int _rnkv,int _szu,int _szv)
	{
		u=_u;
		v=_v;
		rnku=_rnku;
		rnkv=_rnkv;
		szu=_szu;
		szv=_szv;
	}
};
save lol[MAXM];
int lolsz=0;
int getRoot(int u)
{
	if(u==par[u])return u;
	return getRoot(par[u]);
}
void join_wr(int u,int v)
{
	lol[lolsz++]=save(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 join(int u,int v)
{
	//lol[lolsz++]=save(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[--lolsz];
	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].emplace_back(query(t,b,-r));
		}
		if(t==2)
		{
			int w,s;
			cin>>s>>w;
			blocks[cb].push_back(query(t,s,-w));
		}
		ans[i]=-1;
	}
	int s=0;
	vector<edge>unchanged;vector<query1>a;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(query1(j+s,blocks[i][j].a,blocks[i][j].b));
			}
		}
		sort(a.begin(),a.end());
		used_edges=0;
		int pp=0;
		for(int j=0;j<a.size();++j)
		{
			used_edges=0;
			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_wr(n1,n2);
						used_edges++;
					}
					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_wr(n1,n2);
					used_edges++;
				}
				used[idx]=1;
			}
			ans[a[j].time]=sz[getRoot(a[j].s)];
			for(int l=0;l<used_edges;++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;
}

컴파일 시 표준 에러 (stderr) 메시지

bridges.cpp: In function 'int main()':
bridges.cpp:201:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<query1>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  201 |   for(int j=0;j<a.size();++j)
      |               ~^~~~~~~~~
bridges.cpp:204:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |    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