Submission #570607

#	Time	Username	Problem	Language	Result	Execution time	Memory
570607		Dat160601	Bridges (APIO19_bridges)	C++17	13 / 100	433 ms	524288 KiB

bridges

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second

const int N = 1e5 + 7;

int n, m, q, s[N], t[N], wt[N], it[2 * N], pset[N], ans[N];
bool sub2 = true, vis[N];
int type, a, b;
vector < pair < int, pair <int, int> > > query, ed;
vector < pair <int, int> > edge[N];

void init(int k, int l, int r){
	if(l == r){
		it[k] = wt[l];
		return;
	}
	int mid = (l + r) >> 1;
	init(k << 1, l, mid);
	init(k << 1 | 1, mid + 1, r);
	it[k] = min(it[k << 1], it[k << 1 | 1]);
}

void update(int k, int l, int r, int pos, int val){
	if(l > pos || r < pos) return;
	if(l == r){
		it[k] = val;
		return;
	}
	int mid = (l + r) >> 1;
	update(k << 1, l, mid, pos, val);
	update(k << 1 | 1, mid + 1, r, pos, val);
	it[k] = min(it[k << 1], it[k << 1 | 1]);
}

int get(int k, int l, int r, int L, int R){
	if(l > R || r < L || L > R) return (int)1e9;
	if(l >= L && r <= R) return it[k];
	int mid = (l + r) >> 1;
	return min(get(k << 1, l, mid, L, R), get(k << 1 | 1, mid + 1, r, L, R));
}

int fset(int x){
	if(pset[x] < 0) return x;
	return pset[x] = fset(pset[x]);
}

void unionset(int x, int y){
	x = fset(x), y = fset(y);
	if(x == y) return;
	pset[x] += pset[y];
	pset[y] = x;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	if(m != n - 1) sub2 = false;
	for(int i = 1; i <= m; i++){
		cin >> s[i] >> t[i] >> wt[i];
		if(s[i] != i || t[i] != i + 1) sub2 = false;
	}
	cin >> q;
	if(n <= 1000 && m <= 1000 && q <= 10000){
		for(int i = 1; i <= q; i++){
			cin >> type >> a >> b;
			if(type == 1) wt[a] = b;
			else{
				for(int i = 1; i <= n; i++) edge[i].clear(), vis[i] = false;
				for(int i = 1; i <= m; i++){
					edge[s[i]].pb(mp(t[i], wt[i]));
					edge[t[i]].pb(mp(s[i], wt[i]));
				}
				int ans = 0;
				vis[a] = true;
				queue <int> q;
				q.push(a);
				while(!q.empty()){
					int u = q.front();
					q.pop();
					ans++;
					for(int i = 0; i < (int)edge[u].size(); i++){
						int v = edge[u][i].fi, w = edge[u][i].se;
						if(b > w || vis[v]) continue;
						q.push(v);
						vis[v] = true;
					}
				}
				cout << ans << "\n";
			}
		}
		return 0;
	}
	else if(sub2){
		init(1, 1, m);
		for(int i = 1; i <= q; i++){
			cin >> type >> a >> b;
			if(type == 1){
				wt[a] = b;
				update(1, 1, m, a, b);
			}
			else{
				int lef = a, rig = a;
				if(a > 1 && wt[a - 1] >= b){
					int l = 1, r = a - 1, mid = (l + r) >> 1;
					while(l < r){
						if(get(1, 1, m, mid, a - 1) >= b) r = mid;
						else l = mid + 1;
						mid = (l + r) >> 1;
					}
					lef = l;
				}
				if(a < n && wt[a] >= b){
					int l = a + 1, r = n, mid = (l + r + 1) >> 1;
					while(l < r){
						if(get(1, 1, m, a, mid - 1) >= b) l = mid;
						else r = mid - 1;
						mid = (l + r + 1) >> 1;
					}
					rig = l;
				}
				cout << rig - lef + 1 << "\n";
			}
		}
		return 0;
	}
	else{
		for(int i = 1; i <= q; i++){
			cin >> type >> a >> b;
			query.pb(mp(-b, mp(a, i)));
		}
		for(int i = 1; i <= m; i++){
			ed.pb(mp(-wt[i], mp(s[i], t[i])));
		}
		for(int i = 1; i <= n; i++) pset[i] = -1;
		sort(query.begin(), query.end());
		sort(ed.begin(), ed.end());
		int now = 0;
		for(int i = 0; i < (int)query.size(); i++){
			int id = query[i].se.se;
			int u = query[i].se.fi;
			int w = -query[i].fi;
			while(now < m && -ed[now].fi >= w){
				unionset(ed[now].se.fi, ed[now].se.se);
				now++;
			}
			ans[id] = -pset[fset(u)];
		}
		for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
	}
}

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