Submission #389847

#	Time	Username	Problem	Language	Result	Execution time	Memory
389847		Blagojce	Bridges (APIO19_bridges)	C++11	59 / 100	3031 ms	11564 KiB

bridges

#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)


using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
const int i_inf = 1e9;
const ll inf = 4e9;
const ll mod = 1e9+7;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;

mt19937 _rand(time(NULL));
clock_t z;

const int mxn = 1e5;
const int bsz = 500;

int n, m, q;

int t[mxn], a[mxn], b[mxn];

int l[mxn], r[mxn], w[mxn];


int neww[mxn];
bool nonstat[mxn];


int link[mxn];
int siz[mxn];
int findx(int x){
	if(x == link[x]) return x;
	link[x] = findx(link[x]);
	return link[x];
}
void unite(int u, int v){
	u = findx(u);
	v = findx(v);
	
	if(u == v) return;
	
	if(siz[u] < siz[v]) swap(u, v);
	link[v] = u;
	siz[u] += siz[v];
}


vector<int> G[mxn];
bool vis[mxn];

int dfs(int u){
	vis[u] = true;
	int ret = siz[u];
	
	for(auto e : G[u]){
		if(!vis[e]){
			ret += dfs(e);
		}
	}
	return ret;
}

int ans[mxn];


void solve(){
	cin >> n >> m;
	fr(i, 0, m){
		cin >> l[i] >> r[i] >> w[i];
		--l[i];
		--r[i];
	}
	cin >> q;
	fr(i, 0, q){
		cin >> t[i] >> a[i] >> b[i];
		--a[i];
		
	}
	
	vector<pair<ll, pair<int,int> > > g;
	vector<int> v;
	
	
	fr(bi, 0, (q+bsz-1)/bsz){
		
		
		
		memset(nonstat, false, sizeof(nonstat));
		g.clear();
		v.clear();
		
		fr(i, 0, n){
			link[i] = i;
			siz[i] = 1;
		}
		
		
		
		fr(i, bi*bsz, min(q, (bi+1)*bsz)){
			if(t[i] == 1){
				nonstat[a[i]] = true;
			}
			else{
				g.pb({-b[i], {1, i}});
			}
		}
		fr(i, 0, m){
			if(!nonstat[i]){
				g.pb({-w[i], {0, i}});
			}
			else{
				v.pb(i);
			}
		}
		sort(all(g));
		for(auto u : g){
			if(u.nd.st == 0){
				unite(l[u.nd.nd], r[u.nd.nd]);
			}
			else{
				for(auto edge : v) neww[edge] = -1;
				
				int pos = u.nd.nd;
				
				fr(i, bi*bsz, min(q, (bi+1)*bsz)){
					if(t[i] != 1) continue;
					if(i < pos){
						neww[a[i]] = b[i];
					}
					else if(neww[a[i]] == -1){
						neww[a[i]] = w[a[i]];
					}
				}
				for(auto edge : v){
					if(neww[edge] >= b[pos]){
						int A = findx(l[edge]);
						int B = findx(r[edge]);
						vis[A] = vis[B] = false;
						
						G[A].pb(B);
						G[B].pb(A);
					}
				}
				
				
				
				ans[pos] = dfs(findx(a[pos]));
				
				for(auto edge : v){
					if(neww[edge] >= b[pos]){
						int A = findx(l[edge]);
						int B = findx(r[edge]);
						G[A].pop_back();
						G[B].pop_back();
					}
				}
			}
		}
		
		fr(i, bi*bsz, min(q, (bi+1)*bsz)){
			if(t[i] == 1){
				w[a[i]] = b[i];
			}
		}
	}
	fr(i, 0, q){
		if(t[i] == 2){
			cout<<ans[i]<<endl;
		}
	}
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();	
}

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