Submission #1032692

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032692		Muhammet	Bridges (APIO19_bridges)	C++17	13 / 100	661 ms	524288 KiB

bridges

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

#define sz(x) (int)x.size()
#define ff first
#define ss second
#define int long long int

const int N = 2000005;
const int M = 1e9 + 7;

int T, n, a[N], b[N], c[N], q, s[N], w[N], t[N], d[N], r2[N], ans, vis[N], m, x3;

vector <pair<int,int>> v[N];

vector <int> st;

void dfs(int x, int y){
	vis[x] = 1;
	ans++;
	for(auto i : v[x]){
		if(vis[i.ff] == 0 and i.ss >= y){
			dfs(i.ff,y);
		}
	}
}

int bld(int nd, int l, int r){
	if(l == r) return st[nd] = c[l];
	int md = (l + r) / 2;
	return st[nd] = min(bld(nd*2,l,md), bld(nd*2+1,md+1,r));
}

int upd(int nd, int l, int r, int ind, int vl){
	if((r < ind) or (l > ind)) return st[nd];
	if(l == r) return st[nd] = vl;
	int md = (l + r) / 2;
	return st[nd] = min(upd(nd*2,l,md,ind,vl), upd(nd*2+1,md+1,r,ind,vl));
}

int fnd(int nd, int l, int r, int x, int y){
	if(l > y or r < x) return st[nd];
	if(l >= x and r <= y){
		x3 = min(x3,st[nd]);
		return st[nd];
	}
	int md = (l + r) / 2;
	return st[nd] = min(fnd(nd*2,l,md,x,y),fnd(nd*2+1,md+1,r,x,y));
}

int32_t main(){
	ios::sync_with_stdio(false); cin.tie(0);

	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> a[i] >> b[i] >> c[i];
	}
	st.resize(m*4);
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i];
		if(t[i] == 1){
			cin >> d[i] >> r2[i];
		}
		else {
			cin >> s[i] >> w[i];
		}
	}

	if(n <= 1000 and m <= 1000 and q <= 10000){
		for(int i = 1; i <= q; i++){
			if(t[i] == 1){
				c[d[i]] = r2[i];
			}
			else {
				for(int j = 1; j <= n; j++){
					v[j].clear();
					vis[j] = 0;
				}
				for(int j = 1; j <= m; j++){
					v[a[j]].push_back({b[j],c[j]});
					v[b[j]].push_back({a[j],c[j]});
				}
				ans = 0;
				dfs(s[i],w[i]);
				cout << ans << '\n';
			}
		}
	}
	else {
		bld(1,1,m);
		for(int i = 1; i <= q; i++){
			if(t[i] == 1){
				upd(1,1,m,d[i],r2[i]);
			}
			else {
				int l1 = s[i], r1 = m, k = 0, an = n;
				while(l1 <= r1){
					int md = (l1 + r1) / 2;
					x3 = 1e9;
					fnd(1,1,m,s[i],md);
					if(x3 < w[i]){
						r1 = md-1;
						k = md;
					}
					else {
						l1 = md+1;
					}
				}
				if(k != 0) an -= (n-k);
				l1 = 1, r1 = s[i]-1, k = 0;
				while(l1 <= r1){
					int md = (l1 + r1) / 2;
					x3 = 1e9;
					fnd(1,1,m,md,s[i]-1);
					if(x3 < w[i]){
						l1 = md+1;
						k = md;
					}
					else {
						r1 = md-1;
					}
				}
				an -= k;
				cout << an << '\n';
			}
		}
	}

	return 0;
}

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