Submission #641907

#	Time	Username	Problem	Language	Result	Execution time	Memory
641907		GusterGoose27	Bridges (APIO19_bridges)	C++11	13 / 100	3090 ms	9304 KiB

bridges

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 5e4;
const int MAXM = 1e5;
int n, m, q;

vector<pii> edges[MAXN];
int weights[MAXM];
bool vis[MAXN];

int dfs(int cur, int mxw) {
	if (vis[cur]) return 0;
	int ans = 1;
	vis[cur] = 1;
	for (pii p: edges[cur]) {
		if (vis[p.first] || weights[p.second] < mxw) continue;
		ans += dfs(p.first, mxw);
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y >> weights[i];
		x--; y--;
		edges[x].push_back(pii(y, i));
		edges[y].push_back(pii(x, i));
	}
	cin >> q;
	for (int i = 0; i < q; i++) {
		int t; cin >> t;
		if (t == 1) {
			int b, r; cin >> b >> r;
			weights[b-1] = r;
		}
		else {
			int s, r; cin >> s >> r;
			s--;
			fill(vis, vis+n, 0);
			cout << dfs(s, r) << "\n";
		}
	}
}

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