제출 #641907

#제출 시각아이디문제언어결과실행 시간메모리
641907GusterGoose27다리 (APIO19_bridges)C++11
13 / 100
3090 ms9304 KiB
#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";
		}
	}
}
#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...