제출 #675849

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
675849		Dan4Life	Bridges (APIO19_bridges)	C++17	0 / 100	1 ms	980 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;
vector<int> adj[maxn];
unordered_map<int,int> wei[maxn];
int vis[maxn], tc;

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

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

void dfs(int s, int weight, int p){
	vis[s]=tc;
	for(auto u : adj[s]){
		int w = wei[s][u];
		if(u==p or w<weight or vis[u]==tc) 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);
		adj[edge[i].b].pb(edge[i].a);
	}
	cin >> q;
	for(int i = 1; i <= q; i++){
		cin >> Q[i].t >> Q[i].x >> Q[i].y; tc=i;
		if(Q[i].t==1){
			auto &cur = edge[Q[i].x]; cur.w= Q[i].y;
			wei[cur.a][cur.b]=wei[cur.b][cur.a]=cur.w;
		}
		else{
			dfs(Q[i].x, Q[i].y, -1); int cnt = 0;
			for(int i = 1; i <= n; i++) cnt+=(vis[i]==tc);
			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