Submission #934028

#	Time	Username	Problem	Language	Result	Execution time	Memory
934028		vjudge1	Bridges (APIO19_bridges)	C++17	14 / 100	159 ms	7508 KiB

bridges

#include <bits/stdc++.h>
using namespace std;

int comp[50005];

int fin(int v) {

    if(comp[v] < 0) {
        return v;
    }

    comp[v] = fin(comp[v]);
    return comp[v];
}

void me(int u, int v) {

    u = fin(u);
    v = fin(v);

    if(u == v) return;

    if(comp[u] < comp[v]) swap(u, v);

    comp[v] += comp[u];
    comp[u] = v;
}

bool cmp(pair<pair<int, int>, pair<int, int>> a, pair<pair<int, int>, pair<int, int>> b) {

	if(a.second.second > b.second.second) return false;

	return true;
}

pair<int, pair<int, int>> ed[100005];

pair<pair<int, int>, pair<int, int>> que[100005];

int main() {
	
	int n, m, a, b, c, q;

	cin >> n >> m;

	 for(int i=0; i<=n; i++) {
        comp[i] = -1;
    }

	for(int i=0; i<m; i++) {
		cin >> a >> b >> c;

		ed[i] = {c, {a, b}};
	}

	sort(ed, ed+m, greater<pair<int, pair<int, int>>>());

	ed[m] = {-1, {1, 1}};

	cin >> q;

	int op;

	for(int i=0; i<q; i++) {
		cin >> op >> a >> b;

		que[i] = {{b, 0}, {a, i}};
	}

	sort(que, que+q, greater<pair<pair<int, int>, pair<int, int>>>());

	int j=0; 

	for(int i=0; i<q; i++) {

		while(ed[j].first >= que[i].first.first) {
			me(ed[j].second.first, ed[j].second.second);
			j++;
		}

		que[i].first.second = -comp[fin(que[i].second.first)];
	}

	sort(que, que+q, cmp);

	for(int i=0; i<q; i++) {
		cout << que[i].first.second << "\n";
	}

	/*for(int i=0; i<=n; i++) {
		cout << comp[i] << " ";
	}*/
	
}

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