Submission #382995

#	Time	Username	Problem	Language	Result	Execution time	Memory
382995		milleniumEeee	다리 (APIO19_bridges)	C++17	14 / 100	326 ms	10804 KiB

bridges

#include <bits/stdc++.h>
#define fastInp ios_base::sync_with_stdio(0); cin.tie(0);
#define pii pair<int, int>
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
using namespace std;

const int MAXN = (int)1e5 + 5;
const int INF = (int)2e9 + 7;
const int L = 20;

vector <pii> g[MAXN];
int edge[MAXN];
int n, m, q;
int ans[MAXN];

struct Query {
	int type, x, y, ind;
	Query (int type_, int x_, int y_) {
		type = type_;
		x = x_;
		y = y_;
	}
	Query () {
		
	}
	const bool operator < (const Query &other) {
		return y < other.y;
	}
};

Query qr[MAXN];

int pr[MAXN], sz[MAXN];

int findp(int v) {
	if (v == pr[v]) {
		return v;
	}
	return pr[v] = findp(pr[v]);
}

void unite(int a, int b) {
	a = findp(a);
	b = findp(b);
	if (a == b) {
		return;
	}
	if (sz[a] > sz[b]) {
		swap(a, b);
	}
	sz[b] += sz[a];
	pr[a] = b;
}

signed main() {
	fastInp;
	fill(sz, sz + MAXN, 1);
	iota(pr, pr + MAXN, 0);
	cin >> n >> m;
	vector <pair<int, pii>> vec;
	for (int i = 1; i <= m; i++) {
		int u, v, val;
		cin >> u >> v >> val;
		edge[i] = val;
		vec.pb({val, {u, v}});
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		cin >> qr[i].type >> qr[i].x >> qr[i].y;
		qr[i].ind = i;
	}
	sort(qr + 1, qr + q + 1);
	int pos = szof(vec);
	sort(all(vec));
	for (int i = q; i >= 1; i--) {
		while (pos > 0 && vec[pos - 1].fr >= qr[i].y) {
			unite(vec[pos - 1].sc.fr, vec[pos - 1].sc.sc);
			pos--;
		}
		ans[qr[i].ind] = sz[findp(qr[i].x)];
	}
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << endl;
	}
}
/*
4 5 
1 2 10
1 3 6
3 2 9
3 4 7
2 4 15
1

*/

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