제출 #1031794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1031794		Muhammet	다리 (APIO19_bridges)	C++17	13 / 100	528 ms	13652 KiB

bridges

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

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

const ll N = 300005;
const ll M = 1e9 + 7;

int T, n, a[N], b[N], c[N], q, s[N], w[N], t[N], d[N], r[N], ans, vis[N], m, st[N*4];

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

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] = max(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(l == r) return st[nd] = vl;
	if((r < ind) or (l > ind)) return st[nd];
	int md = (l + r) / 2;
	return st[nd] = max(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 >= x and r <= y) return st[nd];
	if(l > y or r < x) return 0;
	int md = (l + r) / 2;
	return max(fnd(nd*2,l,md,x,y),fnd(nd*2+1,md+1,r,x,y));
}

int 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];
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> t[i];
		if(t[i] == 1){
			cin >> d[i] >> r[i];
		}
		else {
			cin >> s[i] >> w[i];
		}
	}

	if(n <= 1000 and m <= 1000 and q <= 10000){
		for(int i = 1; i <= q; i++){
			for(int j = 1; j <= n; j++){
				v[j].clear();
				vis[j] = 0;
			}
			if(t[i] == 1){
				c[d[i]] = r[i];
			}
			else {
				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],r[i]);
			}
			else {
				int l1 = s[i], r1 = m, k = 0, an = n-1;
				while(l1 <= r1){
					int md = (l1 + r1) / 2;
					if(fnd(1,1,m,s[i],md) > 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;
					if(fnd(1,1,m,md,s[i]-1) > 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