Submission #675853

#TimeUsernameProblemLanguageResultExecution timeMemory
675853Dan4LifeBridges (APIO19_bridges)C++17
0 / 100
2 ms1748 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,unordered_map<int,int>> wei;
int vis[maxn], tc;
unordered_map<int,unordered_map<int,multiset<int>>> S;
struct query{
	int t, x, y;
} Q[maxn*10];

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

void dfs(int s, int weight, int p){
	vis[s]=tc;
	for(auto u : adj[s]){
		int w = wei[min(s,u)][max(s,u)];
		if(u==p or weight>w 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 >> e[i].a >> e[i].b >> e[i].w;
		int &a = e[i].a, &b = e[i].b, &w = e[i].w; if(a>b) swap(a,b);
		if(!wei[a].count(b)) wei[a][b]=w;
		else wei[a][b]=max(w,wei[a][b]);
		S[a][b].insert(w);
		adj[a].pb(b); adj[b].pb(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){
			int j = Q[i].x; 
			int &a = e[j].a, &b = e[j].b, &w = e[j].w;
			S[a][b].erase(S[a][b].find(w)); S[a][b].insert(Q[i].y);
			wei[a][b]=*prev(S[a][b].end());
		}
		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...