Submission #484909

#	Time	Username	Problem	Language	Result	Execution time	Memory
484909		MilosMilutinovic	Bridges (APIO19_bridges)	C++14	100 / 100	2468 ms	210768 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
const int BLOCK=800;
int n,m,q,u[N],v[N],w[N],t[N],x[N],y[N],ans[N];
vector<int> qs[BLOCK+5];
bool vis[N];
struct Dsu{
	int p[N],sz[N];
	void init(){
		for(int i=1;i<=n;i++){
			p[i]=i;
			sz[i]=1;
		}
	}
	int root(int u){
		return p[u]==u?u:root(p[u]);
	}
	stack<tuple<int,int,int,int>> stk;
	void unite(int u,int v){
		u=root(u);
		v=root(v);
		if(sz[u]<sz[v])swap(u,v);
		stk.push({u,v,sz[u],sz[v]});
		if(u==v)return;
		p[v]=u;
		sz[u]+=sz[v];
	}
	void rollback(){
		auto op=stk.top();
		stk.pop();
		int u=get<0>(op);
		int v=get<1>(op);
		p[u]=u;
		p[v]=v;
		sz[u]=get<2>(op);
		sz[v]=get<3>(op);
	}
}d;
signed main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
	}
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&t[i],&x[i],&y[i]);
	}
	for(int l=1;l<=q;l+=BLOCK){
		int r=min(q,l+BLOCK-1);
		for(int i=0;i<=BLOCK;i++)qs[i].clear();
		for(int id=1;id<=m;id++)vis[id]=false;
		d.init();
		vector<int> edg,ver;
		for(int i=l;i<=r;i++)if(t[i]==1)edg.push_back(x[i]);
		for(int i=l;i<=r;i++){
			if(t[i]==1){
				vis[x[i]]=true;
				w[x[i]]=y[i];
			}else{
				for(int id:edg)if(w[id]>=y[i])qs[i-l].push_back(id);
				ver.push_back(i);
			}
		}
		vector<int> unu;
		for(int id=1;id<=m;id++)if(!vis[id])unu.push_back(id);
		sort(ver.begin(),ver.end(),[&](int i,int j){
			return y[i]>y[j];
		});
		sort(unu.begin(),unu.end(),[&](int i,int j){
			return w[i]>w[j];
		});
		int ptr=0;
		for(int i=0;i<(int)ver.size();i++){
			int pos=ver[i],bd=pos-l;
			while (ptr<unu.size()&&y[pos]<=w[unu[ptr]]){
				d.unite(u[unu[ptr]],v[unu[ptr]]);
				ptr++;
			}
			for(int id:qs[bd])d.unite(u[id],v[id]);
			ans[pos]=d.sz[d.root(x[pos])];
			for(int id:qs[bd])d.rollback();
		}
	}
	for(int i=1;i<=q;i++){
		if(t[i]==2){
			printf("%d\n",ans[i]);
		}
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:76:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    while (ptr<unu.size()&&y[pos]<=w[unu[ptr]]){
      |           ~~~^~~~~~~~~~~
bridges.cpp:82:12: warning: unused variable 'id' [-Wunused-variable]
   82 |    for(int id:qs[bd])d.rollback();
      |            ^~
bridges.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
bridges.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d%d",&u[i],&v[i],&w[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
bridges.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |   scanf("%d%d%d",&t[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