제출 #567796

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
567796		8e7	다리 (APIO19_bridges)	C++17	17 / 100	3062 ms	524288 KiB

bridges

//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T,class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
vector<pii> adj[maxn];
int siz[maxn], head[maxn];
vector<int> f[maxn];

int wei[maxn];
pii ed[maxn];
void dfs(int n, int par, int d) {
	siz[n] = 1;
	if (d < 7) head[n] = 1; 
	else if (d == 7) head[n] = n;
	for (auto [v, w]:adj[n]) {
		if (v != par) {
			head[v] = head[n];
			dfs(v, n, d + 1);
			siz[n] += siz[v];
		}
	}
}
void getdis(int n, int par, vector<int> &vec, int mi) {
	vec.push_back(mi);
	for (auto [v, w]:adj[n]) {
		if (v != par && head[v] == head[n]) {
			getdis(v, n, vec, min(mi, wei[w]));
		}
	}
}
void getans(int n, int par, int wi, int &ans) {
	ans++;
	for (auto [v, w]:adj[n]) {
		if (v != par && wei[w] >= wi) {
			if (head[n] == 1 && head[v] != 1) {
				ans += f[v].size() - (lower_bound(f[v].begin(), f[v].end(), wi) - f[v].begin());
				continue;
			} else {
				getans(v, n, wi, ans);
			}
		}
	}
}
int main() {
	io
	int n, m;
	cin >> n >> m;
	for (int i = 0;i < m;i++) {
		int u, v, w;
		cin >> u >> v >> w;
		ed[i] = {u, v};
		adj[u].push_back({v, i});
		adj[v].push_back({u, i});
		wei[i] = w;
	}
	dfs(1, 0, 0);
	for (int i = 1;i <= n;i++) {
		if (head[i] == i) {
			getdis(i, 0, f[i], inf);
			sort(f[i].begin(), f[i].end());
		}
	}
	int q;
	cin >> q;
	while (q--) {
		int type; cin >> type;
		if (type == 1) {
			int bi, ri;
			cin >> bi >> ri;
			bi--;
			wei[bi] = ri;
			if (head[ed[bi].ff] != 1 && head[ed[bi].ss] != 1) {
				int id = head[ed[bi].ff];
				f[id].clear();	
				getdis(id, 0, f[id], inf);
				sort(f[id].begin(), f[id].end());
			}
		} else {
			int s, w;
			cin >> s >> w;
			int ans = 0;
			getans(s, 0, w, ans);
			cout << ans << "\n";
		}
	}
}
/*
7 6
1 2 4
1 3 5
2 4 2
2 5 1
3 6 7
3 7 3
5
2 3 3
1 4 3
2 3 5
2 2 2
2 1 6
*/

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