Submission #249126

#TimeUsernameProblemLanguageResultExecution timeMemory
249126crossing0verBridges (APIO19_bridges)C++17
13 / 100
3078 ms9088 KiB
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e4+5;
struct bridge{
	int a,b,val;
	bridge(){
		a = b = val = 0;
	}
};
int n,m,q;
bool vis[N];
vector<bridge> e;
vector< pair<int,int> > adj[N];
int dfs(int v,int val) {
	int cnt = 1;
	vis[v] = 1;
	for (auto i : adj[v]) {
		if (i.second >= val && !vis[i.first])
			cnt += dfs(i.first,val);
	}
	return cnt;
}
main() {
	cin >> n >> m;
	e.resize(m+1);
	for (int i = 1; i <= m; i++) {
		cin >> e[i].a >> e[i].b >> e[i].val;
		adj[e[i].a].pb({e[i].b,e[i].val});
		adj[e[i].b].pb({e[i].a,e[i].val});
	}
	cin >> q;
	for (int type,x,y;q--;) {
		cin >> type >> x >> y;
		if (type == 1) {
			int a = e[x].a, b = e[x].b,val = e[x].val;
			adj[a].erase(find(adj[a].begin(),adj[a].end(),make_pair(b,val)));
			adj[b].erase(find(adj[b].begin(),adj[b].end(),make_pair(a,val)));
			e[x].val = y;
			adj[a].pb({b,y});
			adj[b].pb({a,y});
		}
		else {
			cout << dfs(x,y) <<'\n';
			fill(vis,vis+n+1,0);
		}
	}
	
}

Compilation message (stderr)

bridges.cpp:24:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
#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...