Submission #675849

#TimeUsernameProblemLanguageResultExecution timeMemory
675849Dan4LifeBridges (APIO19_bridges)C++17
0 / 100
1 ms980 KiB
#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";
		}
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...