Submission #1069717

#	Time	Username	Problem	Language	Result	Execution time	Memory
1069717		vjudge1	Bridges (APIO19_bridges)	C++17	14 / 100	80 ms	26156 KiB

bridges

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

#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()

const ll N = 3e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll n,m,q;
ll c[N], p[N], sz[N];
bool vs[N];
vector<pll>adj[N];
struct edge{ll u,v,c;} e[N];
struct ccjv{ll s,w,idx;} t[N];
void sub1(){
	for(int i = 1; i <= m;i++){
		ll u,v,w; cin >> u >> v >> w;
		adj[u].pb({v, i}), adj[v].pb({u, i});
		c[i] = w;
	}
	cin >> q;
	while(q--){
		ll typ; cin >> typ;
		if(typ == 1){
			ll x,y; cin >> x >> y;
			c[x] = y;
		}
		else{
			ll s,w; cin >> s >> w;
			for(int i = 1; i <= n;i++) vs[i] = 0;
			vs[s] = 1;
			queue<ll>q;
			q.push(s);
			while(q.size()){
				ll u = q.front();q.pop();
				for(auto v : adj[u]){
					if(vs[v.F] || w > c[v.S]) continue;
					vs[v.F] = 1;
					q.push(v.F);
				}
			}
			ll res = 0;
			for(int i = 1; i <= n;i++) if(vs[i]) res++;
			cout << res << "\n";
		}
	}
}
ll find(ll v){
	return (v == p[v] ? v : p[v] = find(p[v]));
}
void join(ll u, ll v){
	u = find(u), v = find(v);
	if(u == v) return;
	if(sz[u] < sz[v]) swap(u, v);
	p[v] = u, sz[u] += sz[v];
}
void sub4(){
	for(int i = 1; i <= m;i++) cin >> e[i].u >> e[i].v >> e[i].c;
	sort(e + 1, e + m + 1, [&](const edge &a, const edge &b){
		return a.c > b.c;
	});
	cin >> q;
	for(int i = 1; i <= q;i++){
		ll typ; cin >> typ;
		cin >> t[i].s >> t[i].w;
		t[i].idx = i;
	}
	sort(t + 1, t + q + 1, [&](const ccjv &a, const ccjv &b){
		return a.w > b.w;
	});
	vector<ll>res(q + 10);
	ll j = 1;
	for(int i = 1; i <= n;i++) p[i] = i, sz[i] = 1;
	for(int i = 1; i <= q;i++){
		while(j <= m && e[j].c >= t[i].w){
			join(e[j].u, e[j].v);
			j++;
		}
		res[t[i].idx] = sz[find(t[i].s)];
	}
	for(int i = 1; i <= q;i++) cout << res[i] << '\n';
}
void to_thic_cau(){ 
	cin >> n >> m;
	//sub1();
	sub4();
}    


signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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