Submission #980918

#	Time	Username	Problem	Language	Result	Execution time	Memory
980918		kayn	Bridges (APIO19_bridges)	C++14	13 / 100	80 ms	8340 KiB

bridges

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define run ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int MX=100010;
int n, m, q, vis[MX],  w[MX];
vector<pii> adj[MX];
map<int, map<int, int>> id;

void bfs(int start, int wg, int idx){
	queue<int> q;
	q.push(start);
	int cn=-1, ans=0;
	while(!q.empty()){
		cn=q.front(); 
//		cout << cn << endl;
		q.pop();
		if(vis[cn]==idx) continue;
		vis[cn]=idx; ans++;
		for(auto i : adj[cn]){
			int nn=i.fi, ni=i.se;
			if(w[ni]<wg || vis[nn]==idx) continue;
			q.push(nn);
		}
	}
	cout << ans << endl;
}

void sub1(){
	int t, b, r;
	for(int i=1; i<=q; i++){
		cin >> t >> b >> r;
		if(t==1){
			w[b]=r;
		}
		else{
			bfs(b, r, i);
		}
	}
}

void sub2(){
	
}

int main(){
	cin >> n >> m;
	int u, v, d;
	for(int i=1; i<=m; i++){
		cin >> u >> v >> d;
		adj[u].pb({v, i}); adj[v].pb({u, i});
//		id[v][u]=i;
//		id[u][v]=i;
		w[i]=d;
	}
	cin >> q;
	if(n<=1000 && m<=1000 && q<=10000) sub1();
	else sub2();
	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