Submission #572452

#	Time	Username	Problem	Language	Result	Execution time	Memory
572452		CpDark	Bridges (APIO19_bridges)	C++14	13 / 100	3077 ms	12116 KiB

bridges

#include <bits/stdc++.h>
#define fastInput ios::sync_with_stdio(false); cin.tie(nullptr);

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pii;
typedef vector<pii> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;

vector<vp> graph;
vll weight;

vb visited;

void dfs(int v, int k) {
	visited[v] = true;
	for (int i = 0; i < graph[v].size(); i++) {
		int u = graph[v][i].first;
		ll w = weight[graph[v][i].second];
		if (k <= w && !visited[u]) {
			dfs(u, k);
		}
	}
}

int main() {
	fastInput;
	int n, m;
	cin >> n >> m;

	graph.resize(n + 1);
	weight.resize(m + 1);
	int a, b, d;
	for (int i = 1; i <= m; i++) {
		cin >> a >> b >> d;
		graph[a].push_back({ b,i });
		graph[b].push_back({ a,i });
		weight[i] = d;
	}

	visited.resize(n + 1,false);

	int q;
	cin >> q;
	int t;
	for (int i = 0; i < q; i++) {
		cin >> t;
		if (t == 1) {
			 int r;
			 cin >> b >> r;
			 weight[b] = r;
		}
		else {
			int s, w;
			cin >> s >> w;
			dfs(s, w);
			int ans = 0;
			for (int i = 1; i <= n; i++) {
				if (visited[i]) {
					ans++;
					visited[i] = false;
				}
			}
			cout << ans << endl;
		}
	}


	return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'void dfs(int, int)':
bridges.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |  for (int i = 0; i < graph[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~~

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