Submission #675845

#	Time	Username	Problem	Language	Result	Execution time	Memory
675845		Dan4Life	Bridges (APIO19_bridges)	C++17	0 / 100	2 ms	1128 KiB

bridges

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

const int maxn = (int)1e3+10;

int n, m, q, cnt=0;
vector<pair<int,int>> adj[maxn];
unordered_map<int,int> wei[maxn];
bool vis[maxn];

struct query{
	int t, x, y;
} Q[maxn];

struct Edge{
	int a, b, w;
} edge[maxn];

void dfs(int s, int weight, int p){
	cnt++; vis[s]=1;
	for(auto cur : adj[s]){
		int u = cur.fi, w = wei[s][u];
		if(u==p or w<weight or vis[u]) continue;
		dfs(u,weight,s);
	}
}

int32_t main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		cin >> edge[i].a >> edge[i].b >> edge[i].w;
		wei[edge[i].a][edge[i].b]=wei[edge[i].b][edge[i].a]=edge[i].w;
		adj[edge[i].a].pb({edge[i].b,edge[i].w});
		adj[edge[i].b].pb({edge[i].a,edge[i].w});
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> Q[i].t >> Q[i].x >> Q[i].y;
		if(Q[i].t==1){
			auto &cur = edge[Q[i].t]; cur.w= Q[i].y;
			wei[cur.a][cur.b]=wei[cur.b][cur.a]=cur.w;
		}
		else{
			fill(vis,vis+maxn,false);
			cnt = 0; dfs(Q[i].x, Q[i].y, -1); 
			cout << cnt << "\n";
		}
	}
}

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