제출 #1277679

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1277679		WH8	다리 (APIO19_bridges)	C++20	14 / 100	3094 ms	19660 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define ld long double
const int blk=10005;
int n,m,q;
vector<int> sz(50005, 1), p(50005, 0), res(100001, 0), firstchange(50005, 0);
int u[100001], v[100001], w[100001];
int t[100001], x[100001], y[100001];
vector<vector<int>> al(50005);
bool changed[100001];
vector<bool> vis(50005, 0);
int par(int x){
	if(p[x]==0)return x;
	return p[x]=par(p[x]);
}
void merge(int x, int y){
	int a=par(x), b=par(y);
	if(a==b)return;
	p[a]=b;
	sz[b]+=sz[a];
}



signed main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>u[i]>>v[i]>>w[i];
	int q;cin>>q;
	for(int i=1;i<=q;i++)cin>>t[i]>>x[i]>>y[i];
	for(int l=1;l<=q;l+=blk){
		int r=min(q+1, l+blk); // answer [l, r) queries. 
		//reset
		fill(changed, changed+m+1, false);
		fill(p.begin(),p.end(), 0);
		fill(sz.begin(),sz.end(), 1);
// weight, type, position, 
// 20, unchanged 0, edge index. 
// 19, query 1, query position. 
// loop through the current block changed before query position. 
// and add to adj list
// dfs from head of current guy. 
// rollback additions to adj list
		vector<tuple<int,int,int>> ev;

		for(int i=l;i<r;i++){
			if(t[i]==1){
				changed[x[i]]=true;
				firstchange[x[i]]=(firstchange[x[i]] < l ? i : min(firstchange[x[i]], i));
			}
			else ev.pb({y[i], 0, i}); 
		}
		
		for(int i=1;i<=m;i++){
			if(!changed[i])ev.pb({w[i], 1, i});
		}
		sort(ev.begin(),ev.end(),greater<tuple<int,int,int>>());
		for(auto [cw, type, ind]: ev){
			if(type==1){
				merge(u[ind], v[ind]);
			}
			else {
				//~ printf("answering %lld %lld query index is %lld\n", cw, type, ind);
				//~ for(int i=1;i<=n;i++)cout<<par(i)<<" ";
				//~ cout<<endl;
				vector<int> ral, rvis;
				for(int i=l;i<r;i++){
					//~ if(t[i]==1)printf("first change %lld, current weight is %lld\n", firstchange[x[i]], w[x[i]]);
					if(t[i]==1 and ((i <= ind and y[i] >= cw) or (firstchange[x[i]] > ind and w[x[i]] >= cw))){

						int px=par(u[x[i]]), py=par(v[x[i]]);
						al[px].pb(py);
						al[py].pb(px);
						ral.pb(px);
						ral.pb(py);
						//~ printf("adding al edge position %lld, u[i] %lld, v[i] %lld: par %lld to par %lld\n", i, u[x[i]], v[x[i]], px, py);
					}
				}
				
				int ans=0;
				auto dfs = [&](auto dfs, int x) -> void{
					vis[x]=true;
					ans+=sz[x];
					rvis.pb(x);
					for(auto it:al[x]){
						if(vis[it])continue;
						dfs(dfs, it);
					}
				};
				dfs(dfs, par(x[ind]));
				for(auto it: ral){
					al[it].clear();
				}
				for(auto it: rvis){
					vis[it]=false;
				}
				res[ind]=ans;
			}
		}
		// implement the actual changes;
		for(int i=l;i<r;i++){
			if(t[i]==1){
				w[x[i]]=y[i];
			}
		}
	}
	for(int i=1;i<=q;i++){
		if(t[i]==2){
			cout<<res[i]<<"\n";
		}
	}
				
		
		
}

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