oj.uz

Submission #926327

# Submission time Handle Problem Language Result Execution time Memory
926327 2024-02-12T19:28:25 Z TAhmed33 Bridges (APIO19_bridges) C++
14 / 100
 169 ms 8244 KB 
#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[0]) {
            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';
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 4080 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 4192 KB Output is correct
2 Correct 68 ms 5288 KB Output is correct
3 Correct 77 ms 4628 KB Output is correct
4 Correct 72 ms 4640 KB Output is correct
5 Correct 140 ms 6536 KB Output is correct
6 Correct 161 ms 8036 KB Output is correct
7 Correct 116 ms 6668 KB Output is correct
8 Correct 114 ms 6724 KB Output is correct
9 Correct 126 ms 6776 KB Output is correct
10 Correct 129 ms 6848 KB Output is correct
11 Correct 132 ms 7184 KB Output is correct
12 Correct 137 ms 7360 KB Output is correct
13 Correct 127 ms 7300 KB Output is correct
14 Correct 124 ms 6604 KB Output is correct
15 Correct 116 ms 6592 KB Output is correct
16 Correct 148 ms 7932 KB Output is correct
17 Correct 151 ms 8244 KB Output is correct
18 Correct 169 ms 7944 KB Output is correct
19 Correct 151 ms 8132 KB Output is correct
20 Correct 136 ms 7644 KB Output is correct
21 Correct 129 ms 7620 KB Output is correct
22 Correct 145 ms 8072 KB Output is correct
23 Correct 117 ms 6524 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4140 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -