Submission #545256

#	Time	Username	Problem	Language	Result	Execution time	Memory
545256		amunduzbaev	Bridges (APIO19_bridges)	C++17	29 / 100	3078 ms	5196 KiB

bridges

#include "bits/stdc++.h"
using namespace std;

#define ar array

namespace sub1{
const int N = 5e4 + 5;
vector<int> edges[N];

void solve(int n, int m, int q, vector<ar<int, 3>>& e){
	while(q--){
		int t; cin>>t;
		if(t == 1){
			int j, w; cin>>j>>w;
			e[--j][2] = w;
		} else {
			int a, w; cin>>a>>w;
			for(int i=0;i<m;i++){
				if(e[i][2] >= w){
					edges[e[i][0]].push_back(e[i][1]);
					edges[e[i][1]].push_back(e[i][0]);
				}
			}
			
			int cnt = 0;
			vector<int> used(n + 1);
			function<void(int)> dfs = [&](int u){
				used[u] = 1, cnt++;
				for(auto x : edges[u]){
					if(!used[x]) dfs(x);
				}
			};
			dfs(a);
			cout<<cnt<<"\n";
			for(int i=1;i<=n;i++) edges[i].clear();
		}
	}
}

};

namespace sub2{

const int B = 230;
int mn[B];

void solve(int n, int m, int q, vector<ar<int, 3>>& e){
	vector<int> a(m);
	for(int i=0;i<m;i++){
		a[--e[i][0]] = e[i][2];
	}
	
	auto rec = [&](int b){
		int l = b * B, r = min((b + 1) * B, m);
		mn[b] = 1e9;
		for(int j=l;j<r;j++){
			mn[b] = min(mn[b], a[j]);
		}
	};
	
	for(int b=0;b<B;b++){
		rec(b);
	}
	
	while(q--){
		int t; cin>>t;
		if(t == 1){
			int i, w; cin>>i>>w;
			a[--i] = w;
			rec(i / B);
		} else {
			int i, w; cin>>i>>w, i--;
			int b = i / B;
			int lx = -1, rx = m;
			for(int j = b * B; j < i;j++){
				if(a[j] < w) lx = max(lx, j);
			}
			
			for(int j=i;j<min(m, (b + 1) * B);j++){
				if(a[j] < w) rx = min(rx, j);
			}
			
			for(int j=b-1;~j;j--){
				if(mn[j] >= w) continue;
				for(int l=j*B;l<(j+1)*B;l++){
					if(a[l] < w) lx = max(lx, l);
				} break;
			}
			
			for(int j=b+1;j<B;j++){
				if(mn[j] >= w) continue;
				for(int l=j*B;l<min(m, (j+1)*B);l++){
					if(a[l] < w) rx = min(rx, l);
				} break;
			}
			
			cout<<rx - lx<<"\n";
		}
	}
}

};

namespace sub3{

void solve(int n, int m, int q, vector<ar<int, 3>>& e){
	vector<int> par(n + 1), sz(n + 1, 1), p(q);
	iota(par.begin(), par.end(), 0);
	vector<ar<int, 2>> qq(q);
	vector<int> res(q);
	for(int i=0;i<q;i++){ cin>>p[i], p[i] = i;
		cin>>qq[i][0]>>qq[i][1];
	}
	
	sort(p.begin(), p.end(), [&](int i, int j){
		return (qq[i][1] > qq[j][1]);
	});
	
	sort(e.begin(), e.end(), [&](auto& a, auto& b){
		return (a[2] > b[2]);
	});
	
	function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
	auto merge = [&](int a, int b){
		a = f(a), b = f(b);
		if(a == b) return;
		if(sz[a] < sz[b]) swap(a, b);
		sz[a] += sz[b];
		par[b] = a;
	};
	
	int l=0;
	for(auto i : p){
		while(l<m && e[l][2] >= qq[i][1]){
			merge(e[l][0], e[l][1]);
		}
		
		res[i] = sz[f(qq[i][0])];
	}
	
	for(int i=0;i<q;i++) cout<<res[i]<<"\n";
}

};

signed main(){
	ios::sync_with_stdio(0); cin.tie(0); 
	
	int n, m; cin>>n>>m;
	vector<ar<int, 3>> e(m);
	bool is = 1;
	for(int i=0;i<m;i++){
		int a, b, c; cin>>a>>b>>c;
		e[i] = {a, b, c};
		if(a != i + 1 || b != i + 2) is = 0;
	}
	
	int q; cin>>q;
	if(n <= 1000 && m <= 1000 && q <= 10000){
		sub1::solve(n, m, q, e);
		return 0;
	}
	
	if(is){
		sub2::solve(n, m, q, e);
	} else {
		sub3::solve(n, m, q, e);
	}
}

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