Submission #983732

#	Time	Username	Problem	Language	Result	Execution time	Memory
983732		pcc	Bridges (APIO19_bridges)	C++17	43 / 100	368 ms	8324 KiB

bridges

#include <bits/stdc++.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 2e5+10;
const int lim = 3030;
int N,M,Q;
vector<pair<int,pii>> edges;
pair<int,pii> req[mxn];

struct DSU{
	int dsu[mxn],sz[mxn];
	DSU(){}
	void init(int n){
		for(int i = 0;i<n;i++)dsu[i] = i,sz[i] = 1;
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
	}
};

namespace S1{
	DSU dsu;
	void GO(){
		for(int i = 0;i<Q;i++){
			if(req[i].fs == 1){
				int id = req[i].sc.fs,w = req[i].sc.sc;
				edges[id-1].fs = w;
			}
			else{
				dsu.init(N+1);
				for(auto &j:edges){
					if(j.fs>=req[i].sc.sc)dsu.onion(j.sc.fs,j.sc.sc);
				}
				cout<<dsu.sz[dsu.root(req[i].sc.fs)]<<'\n';
			}
		}
		return;
	}
}


namespace S2{
	struct SEG{
#define mid ((l+r)>>1)
#define ls now*2+1
#define rs now*2+2
		int seg[mxn*4];
		void modify(int now,int l,int r,int p,int v){
			if(l == r){
				seg[now] = v;
				return;
			}
			if(mid>=p)modify(ls,l,mid,p,v);
			else modify(rs,mid+1,r,p,v);
			seg[now] = min(seg[ls],seg[rs]);
		}
		int getval(int now,int l,int r,int s,int e){
			assert(e>=s);
			if(l>=s&&e>=r)return seg[now];
			if(mid>=e)return getval(ls,l,mid,s,e);
			else if(mid<s)return getval(rs,mid+1,r,s,e);
			else return min(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
		}
#undef ls
#undef rs
#undef mid
	};
	SEG seg;
	void GO(){
		for(int i = 0;i<N-1;i++){
			seg.modify(0,1,N-1,i+1,edges[i].fs);
		}
		for(int i = 0;i<Q;i++){
			auto [t,_] = req[i];
			auto [a,b] = _;
			if(t == 1){
				seg.modify(0,1,N-1,a,b);
				edges[a-1].fs = b;
			}
			else{
				int lp = a,rp = a;
				int l = 1,r = a-1;
				while(l < r){
					int mid = (l+r)>>1;
					if(seg.getval(0,1,N-1,mid,a-1)>=b)r = mid;
					else l = mid+1;
				}
				if(a!=1&&edges[a-2].fs>=b)lp = l;
				l = a,r = N-1;
				while(l<r){
					int mid = (l+r+1)>>1;
					if(seg.getval(0,1,N-1,a,mid)>=b)l = mid;
					else r = mid-1;
				}
				if(a != N&&edges[a-1].fs>=b)rp = l+1;
				cout<<rp-lp+1<<'\n';
			}
		}
		return;
	}
}

namespace S3{
	int ans[mxn];
	DSU dsu;
	void GO(){
		vector<pair<int,pii>> v;
		for(int i = 0;i<Q;i++){
			int t = req[i].fs;
			auto [a,b] = req[i].sc;
			v.push_back(make_pair(b,pii(a,i)));
		}
		sort(v.rbegin(),v.rend());
		sort(edges.begin(),edges.end());
		dsu.init(N+1);
		for(auto [w,_]:v){
			auto [s,id] = _;
			while(!edges.empty()&&edges.back().fs>=w){
				dsu.onion(edges.back().sc.fs,edges.back().sc.sc);
				edges.pop_back();
			}
			ans[id] = dsu.sz[dsu.root(s)];
		}
		for(int i = 0;i<Q;i++)cout<<ans[i]<<'\n';
		return;
	}
}


int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	bool flag = false;
	for(int i = 0;i<M;i++){
		int a,b,c;
		cin>>a>>b>>c;
		edges.push_back(make_pair(c,pii(a,b)));
	}
	cin>>Q;
	for(int i = 0;i<Q;i++){
		int t,a,b;
		cin>>t>>a>>b;
		req[i] = make_pair(t,pii(a,b));
		if(t == 1)flag = true;
	}
	if(N<=lim&&M<=lim&&Q<=lim*10)S1::GO();
	else if(flag)S2::GO();
	else S3::GO();
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void S3::GO()':
bridges.cpp:124:8: warning: unused variable 't' [-Wunused-variable]
  124 |    int t = req[i].fs;
      |        ^

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