제출 #926324

#제출 시각아이디문제언어결과실행 시간메모리
926324TAhmed33다리 (APIO19_bridges)C++98
0 / 100
146 ms4552 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 25; int n, m; struct DSU { int sze[MAXN], par[MAXN]; void init (int n) { for (int i = 1; i <= n; i++) { sze[i] = 1; par[i] = i; } } int find (int x) { return par[x] == x ? x : par[x] = find(par[x]); } void merge (int a, int b) { a = find(a); b = find(b); if (a == b) return; if (sze[a] > sze[b]) swap(a, b); sze[b] += sze[a]; par[a] = b; } } cur; array <int, 3> p[MAXN]; int ans[MAXN]; int main () { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, c; cin >> a >> b >> c; p[i] = {a, b, c}; } sort(p + 1, p + m + 1, [] (array <int, 3> &x, array <int, 3> &y) { return x[2] > y[2]; }); int ptr = 1; int q; cin >> q; vector <array <int, 3>> queries; for (int i = 1; i <= q; i++) { int a, b; cin >> a >> a >> b; queries.push_back({b, a, i}); } sort(queries.begin(), queries.end()); reverse(queries.begin(), queries.end()); cur.init(n); for (auto i : queries) { while (ptr <= m && p[ptr][2] >= i[2]) { cur.merge(p[ptr][0], p[ptr][1]); ptr++; } ans[i[2]] = cur.sze[cur.find(i[1])]; } for (int i = 1; i <= q; i++) cout << ans[i] << '\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...