Submission #1174357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174357		Gurban	Bridges (APIO19_bridges)	C++20	13 / 100	3095 ms	7752 KiB

bridges

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

using ll = long long;

const int maxn=5e4+5;
const int maxm = 1e5+5;
int n,m,q;
int pos[maxm][2];
int ed[maxm][2];
vector<pair<int,int>>E[maxn];

bool vis[maxn];
int ans;
void dfs(int nd,int wgt){
	vis[nd] = 1;
	ans++;
	for(auto i : E[nd]){
		int to = i.first;
		int d = i.second;
		if(vis[to]) continue;
		if(wgt <= d) dfs(to,wgt);
	}
}

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


	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		int x,y,d;
		cin >> x >> y >> d;
		ed[i][0] = x;
		ed[i][1] = y;
		pos[i][0] = (int)E[x].size();
		pos[i][1] = (int)E[y].size();
		E[x].push_back({y,d});
		E[y].push_back({x,d});
	}

	cin >> q;
	while(q--){
		int tp; cin >> tp;
		if(tp == 1){
			int b,r; cin >> b >> r;
			E[ed[b][0]][pos[b][0]].second = r;
			E[ed[b][1]][pos[b][1]].second = r;
		}
		else {
			int s,w; cin >> s >> w;
			ans = 0;
			memset(vis,0,sizeof(vis));
			dfs(s,w);
			cout<<ans<<'\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