Submission #1031754

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031754		KasymK	Bridges (APIO19_bridges)	C++17	13 / 100	3040 ms	23668 KiB

bridges

#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int MOD = 1e9+7;
const int N = 1e5+5;

multiset<pii> adj[N];
vector<vector<int>> e;
bool vis[N];

void dfs(int x, int w){
	vis[x] = true;
	for(auto it = adj[x].begin(); it != adj[x].end(); ++it)
		if(it->ss >= w and !vis[it->ff])
  			dfs(it->ff, w);
}

int main(){
	// freopen("file.txt", "r", stdin);
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i){
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].insert({v, w});
		adj[v].insert({u, w});
		e.push_back({u, v, w});
	}

	int q;
	scanf("%d", &q);
	vector<int> v;
	while(q--){
		int op, x, y;
		scanf("%d%d%d", &op, &x, &y);
		if(op == 1){
			x--;
			int u = e[x][0], v = e[x][1], w = e[x][2];
			adj[u].erase(adj[u].find({v, w}));
			adj[v].erase(adj[v].find({u, w}));
			w = e[x][2] = y;
			adj[u].insert({v, w});
			adj[v].insert({u, w});
			continue;
		}
		// else if(op == 2){
			dfs(x, y);
			int ans = 0;
			for(int i = 1; i <= n; ++i)
				ans += vis[i], vis[i] = 0;
			printf("%d\n", ans);
		// }
	}
	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
bridges.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
bridges.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   scanf("%d%d%d", &op, &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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