# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1032838 | KasymK | Bridges (APIO19_bridges) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define ll long long
#define pb push_back
#define pii pair<int, int>
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
const int MOD = 1e9+7;
const int N = 1e5+5;
const ll INF = 1e18+1;
vector<int> p, sz;
int fnd(int x) {
return p[x] = (x == p[x] ? x : fnd(p[x]));
}
void uni(int x, int y) {
x = fnd(x); y = fnd(y);
if (x == y) return;
p[x] = y;
sz[y] += sz[x];
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
vector<pair<pii, pii>> v;
while (m--) {
int x, y, d;
scanf("%d%d%d", &x, &y, &d);
v.pb({{d, INT_MAX}, {--x, --y}});
}
int q;
scanf("%d". &q);
for (int i = 0; i < q; i++) {
int t, s, w;
scanf("%d%d%d", &t, &s, &w);
v.pb({{w, i}, {--s, 0}});
}
p.assign(n, 0);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0); // fill inside
sort(all(v));
reverse(all(v));
vector<int> ans(q);
for (auto i : v) {
if (i.ff.ss == INT_MAX)
uni(i.ss.ff, i.ss.ss);
else
ans[i.ff.ss] = sz[fnd(i.ss.ff)];
}
for (auto i : ans)
printf("%d\n", i);
return 0;
}