oj.uz

Submission #563602

# Submission time Handle Problem Language Result Execution time Memory
563602 2022-05-17T16:45:17 Z Ooops_sorry Bridges (APIO19_bridges) C++17
100 / 100
 2829 ms 21344 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld long double
#define ll long long

mt19937 rnd(51);

const int N = 50010, K = 800, M = 1e5 + 10, INF = 1e9;
int par[N], sz[N], Sz = 0;
bool used[M];
array<int, 4> arr[M];
set<pair<int,int>> val[M];

int find_set(int v) {
    while (v != par[v]) {
        v = par[v];
    }
    return v;
}

void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a == b) return;
    if (sz[a] < sz[b]) {
        swap(a, b);
    }
    arr[Sz++] = {b, par[b], a, sz[a]};
    par[b] = a;
    sz[a] += sz[b];
}

void upd(int n) {
    while (Sz > n) {
        auto mas = arr[--Sz];
        par[mas[0]] = mas[1];
        sz[mas[2]] = mas[3];
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LCOAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for (int i = 0; i < N; i++) {
        sz[i] = 1;
        par[i] = i;
    }
    int n, m;
    cin >> n >> m;
    vector<pair<int,int>> e(m);
    vector<int> w(m);
    for (int i = 0; i < m; i++) {
        cin >> e[i].first >> e[i].second >> w[i];
        e[i].first--, e[i].second--;
        val[i].insert({-1, w[i]});
    }
    int q;
    cin >> q;
    vector<array<int, 3>> u(q);
    vector<int> ans(q, -1);
    for (int i = 0; i < q; i++) {
        cin >> u[i][0] >> u[i][1] >> u[i][2];
        u[i][1]--;
        if (u[i][0] == 1) {
            val[u[i][1]].insert({i, u[i][2]});
        }
    }
    for (int i = 0; i < q; i += K) {
        vector<array<int, 3>> qu;
        for (int j = i; j < min(i + K, q); j++) {
            if (u[j][0] == 1) {
                used[u[j][1]] = 1;
            } else {
                qu.pb({u[j][2], u[j][1], j});
            }
        }
        vector<int> a, b;
        for (int j = 0; j < m; j++) {
            if (!used[j]) {
                a.pb(j);
            } else {
                b.pb(j);
            }
        }
        sort(a.begin(), a.end(), [&](int i, int j){return w[i] > w[j];});
        sort(qu.rbegin(), qu.rend());
        int ind = 0;
        for (int j = 0; j < qu.size(); j++) {
            while (ind < a.size() && w[a[ind]] >= qu[j][0]) {
                union_set(e[a[ind]].first, e[a[ind]].second);
                ind++;
            }
            int was = Sz;
            for (auto to : b) {
                auto it = prev(val[to].upper_bound({qu[j][2], INF}));
                if (it->second >= qu[j][0]) {
                    union_set(e[to].first, e[to].second);
                }
            }
            ans[qu[j][2]] = sz[find_set(qu[j][1])];
            upd(was);
        }
        upd(0);
        for (int j = 0; j < min(i + K, q); j++) {
            if (u[j][0] == 1) {
                used[u[j][1]] = 0;
                w[u[j][1]] = u[j][2];
            }
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] != -1) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for (int j = 0; j < qu.size(); j++) {
      |                         ~~^~~~~~~~~~~
bridges.cpp:95:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |             while (ind < a.size() && w[a[ind]] >= qu[j][0]) {
      |                    ~~~~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 58 ms 5888 KB Output is correct
4 Correct 6 ms 5588 KB Output is correct
5 Correct 30 ms 5820 KB Output is correct
6 Correct 28 ms 5828 KB Output is correct
7 Correct 31 ms 5820 KB Output is correct
8 Correct 31 ms 5840 KB Output is correct
9 Correct 32 ms 5816 KB Output is correct
10 Correct 32 ms 5840 KB Output is correct
11 Correct 30 ms 5828 KB Output is correct
12 Correct 30 ms 5824 KB Output is correct
13 Correct 40 ms 5836 KB Output is correct
14 Correct 42 ms 5828 KB Output is correct
15 Correct 32 ms 5836 KB Output is correct
16 Correct 32 ms 5836 KB Output is correct
17 Correct 32 ms 5828 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 13576 KB Output is correct
2 Correct 1692 ms 13864 KB Output is correct
3 Correct 1698 ms 13896 KB Output is correct
4 Correct 1673 ms 13716 KB Output is correct
5 Correct 1660 ms 13840 KB Output is correct
6 Correct 2158 ms 13816 KB Output is correct
7 Correct 2095 ms 13864 KB Output is correct
8 Correct 2141 ms 13676 KB Output is correct
9 Correct 41 ms 7116 KB Output is correct
10 Correct 1318 ms 13668 KB Output is correct
11 Correct 1287 ms 13728 KB Output is correct
12 Correct 1267 ms 11940 KB Output is correct
13 Correct 1448 ms 15500 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1377 ms 12220 KB Output is correct
2 Correct 1147 ms 10160 KB Output is correct
3 Correct 1486 ms 12284 KB Output is correct
4 Correct 1338 ms 12172 KB Output is correct
5 Correct 45 ms 7116 KB Output is correct
6 Correct 1425 ms 12268 KB Output is correct
7 Correct 1275 ms 12168 KB Output is correct
8 Correct 1229 ms 12068 KB Output is correct
9 Correct 783 ms 10628 KB Output is correct
10 Correct 741 ms 10256 KB Output is correct
11 Correct 1014 ms 14032 KB Output is correct
12 Correct 968 ms 14088 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1841 ms 14752 KB Output is correct
2 Correct 41 ms 7120 KB Output is correct
3 Correct 190 ms 12252 KB Output is correct
4 Correct 94 ms 12364 KB Output is correct
5 Correct 968 ms 14868 KB Output is correct
6 Correct 1766 ms 14540 KB Output is correct
7 Correct 973 ms 14620 KB Output is correct
8 Correct 897 ms 11316 KB Output is correct
9 Correct 920 ms 11228 KB Output is correct
10 Correct 944 ms 11336 KB Output is correct
11 Correct 1359 ms 13348 KB Output is correct
12 Correct 1367 ms 13012 KB Output is correct
13 Correct 1384 ms 12992 KB Output is correct
14 Correct 872 ms 14880 KB Output is correct
15 Correct 909 ms 14792 KB Output is correct
16 Correct 1788 ms 14496 KB Output is correct
17 Correct 1809 ms 14776 KB Output is correct
18 Correct 1823 ms 14820 KB Output is correct
19 Correct 1819 ms 14964 KB Output is correct
20 Correct 1554 ms 13676 KB Output is correct
21 Correct 1538 ms 13660 KB Output is correct
22 Correct 1745 ms 14540 KB Output is correct
23 Correct 1056 ms 13332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 13576 KB Output is correct
2 Correct 1692 ms 13864 KB Output is correct
3 Correct 1698 ms 13896 KB Output is correct
4 Correct 1673 ms 13716 KB Output is correct
5 Correct 1660 ms 13840 KB Output is correct
6 Correct 2158 ms 13816 KB Output is correct
7 Correct 2095 ms 13864 KB Output is correct
8 Correct 2141 ms 13676 KB Output is correct
9 Correct 41 ms 7116 KB Output is correct
10 Correct 1318 ms 13668 KB Output is correct
11 Correct 1287 ms 13728 KB Output is correct
12 Correct 1267 ms 11940 KB Output is correct
13 Correct 1448 ms 15500 KB Output is correct
14 Correct 1377 ms 12220 KB Output is correct
15 Correct 1147 ms 10160 KB Output is correct
16 Correct 1486 ms 12284 KB Output is correct
17 Correct 1338 ms 12172 KB Output is correct
18 Correct 45 ms 7116 KB Output is correct
19 Correct 1425 ms 12268 KB Output is correct
20 Correct 1275 ms 12168 KB Output is correct
21 Correct 1229 ms 12068 KB Output is correct
22 Correct 783 ms 10628 KB Output is correct
23 Correct 741 ms 10256 KB Output is correct
24 Correct 1014 ms 14032 KB Output is correct
25 Correct 968 ms 14088 KB Output is correct
26 Correct 1720 ms 13712 KB Output is correct
27 Correct 1963 ms 13768 KB Output is correct
28 Correct 1751 ms 13680 KB Output is correct
29 Correct 1513 ms 13888 KB Output is correct
30 Correct 1938 ms 13572 KB Output is correct
31 Correct 1978 ms 13792 KB Output is correct
32 Correct 1994 ms 13696 KB Output is correct
33 Correct 1749 ms 13684 KB Output is correct
34 Correct 1782 ms 13732 KB Output is correct
35 Correct 1772 ms 13708 KB Output is correct
36 Correct 1538 ms 13800 KB Output is correct
37 Correct 1557 ms 13704 KB Output is correct
38 Correct 1560 ms 13880 KB Output is correct
39 Correct 1072 ms 11860 KB Output is correct
40 Correct 1080 ms 11784 KB Output is correct
41 Correct 1054 ms 11812 KB Output is correct
42 Correct 1287 ms 15580 KB Output is correct
43 Correct 1238 ms 15688 KB Output is correct
44 Correct 1232 ms 15636 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 58 ms 5888 KB Output is correct
4 Correct 6 ms 5588 KB Output is correct
5 Correct 30 ms 5820 KB Output is correct
6 Correct 28 ms 5828 KB Output is correct
7 Correct 31 ms 5820 KB Output is correct
8 Correct 31 ms 5840 KB Output is correct
9 Correct 32 ms 5816 KB Output is correct
10 Correct 32 ms 5840 KB Output is correct
11 Correct 30 ms 5828 KB Output is correct
12 Correct 30 ms 5824 KB Output is correct
13 Correct 40 ms 5836 KB Output is correct
14 Correct 42 ms 5828 KB Output is correct
15 Correct 32 ms 5836 KB Output is correct
16 Correct 32 ms 5836 KB Output is correct
17 Correct 32 ms 5828 KB Output is correct
18 Correct 1743 ms 13576 KB Output is correct
19 Correct 1692 ms 13864 KB Output is correct
20 Correct 1698 ms 13896 KB Output is correct
21 Correct 1673 ms 13716 KB Output is correct
22 Correct 1660 ms 13840 KB Output is correct
23 Correct 2158 ms 13816 KB Output is correct
24 Correct 2095 ms 13864 KB Output is correct
25 Correct 2141 ms 13676 KB Output is correct
26 Correct 41 ms 7116 KB Output is correct
27 Correct 1318 ms 13668 KB Output is correct
28 Correct 1287 ms 13728 KB Output is correct
29 Correct 1267 ms 11940 KB Output is correct
30 Correct 1448 ms 15500 KB Output is correct
31 Correct 1377 ms 12220 KB Output is correct
32 Correct 1147 ms 10160 KB Output is correct
33 Correct 1486 ms 12284 KB Output is correct
34 Correct 1338 ms 12172 KB Output is correct
35 Correct 45 ms 7116 KB Output is correct
36 Correct 1425 ms 12268 KB Output is correct
37 Correct 1275 ms 12168 KB Output is correct
38 Correct 1229 ms 12068 KB Output is correct
39 Correct 783 ms 10628 KB Output is correct
40 Correct 741 ms 10256 KB Output is correct
41 Correct 1014 ms 14032 KB Output is correct
42 Correct 968 ms 14088 KB Output is correct
43 Correct 1841 ms 14752 KB Output is correct
44 Correct 41 ms 7120 KB Output is correct
45 Correct 190 ms 12252 KB Output is correct
46 Correct 94 ms 12364 KB Output is correct
47 Correct 968 ms 14868 KB Output is correct
48 Correct 1766 ms 14540 KB Output is correct
49 Correct 973 ms 14620 KB Output is correct
50 Correct 897 ms 11316 KB Output is correct
51 Correct 920 ms 11228 KB Output is correct
52 Correct 944 ms 11336 KB Output is correct
53 Correct 1359 ms 13348 KB Output is correct
54 Correct 1367 ms 13012 KB Output is correct
55 Correct 1384 ms 12992 KB Output is correct
56 Correct 872 ms 14880 KB Output is correct
57 Correct 909 ms 14792 KB Output is correct
58 Correct 1788 ms 14496 KB Output is correct
59 Correct 1809 ms 14776 KB Output is correct
60 Correct 1823 ms 14820 KB Output is correct
61 Correct 1819 ms 14964 KB Output is correct
62 Correct 1554 ms 13676 KB Output is correct
63 Correct 1538 ms 13660 KB Output is correct
64 Correct 1745 ms 14540 KB Output is correct
65 Correct 1056 ms 13332 KB Output is correct
66 Correct 1720 ms 13712 KB Output is correct
67 Correct 1963 ms 13768 KB Output is correct
68 Correct 1751 ms 13680 KB Output is correct
69 Correct 1513 ms 13888 KB Output is correct
70 Correct 1938 ms 13572 KB Output is correct
71 Correct 1978 ms 13792 KB Output is correct
72 Correct 1994 ms 13696 KB Output is correct
73 Correct 1749 ms 13684 KB Output is correct
74 Correct 1782 ms 13732 KB Output is correct
75 Correct 1772 ms 13708 KB Output is correct
76 Correct 1538 ms 13800 KB Output is correct
77 Correct 1557 ms 13704 KB Output is correct
78 Correct 1560 ms 13880 KB Output is correct
79 Correct 1072 ms 11860 KB Output is correct
80 Correct 1080 ms 11784 KB Output is correct
81 Correct 1054 ms 11812 KB Output is correct
82 Correct 1287 ms 15580 KB Output is correct
83 Correct 1238 ms 15688 KB Output is correct
84 Correct 1232 ms 15636 KB Output is correct
85 Correct 2656 ms 17248 KB Output is correct
86 Correct 253 ms 14644 KB Output is correct
87 Correct 159 ms 14664 KB Output is correct
88 Correct 1790 ms 19404 KB Output is correct
89 Correct 2669 ms 21160 KB Output is correct
90 Correct 1819 ms 19348 KB Output is correct
91 Correct 1838 ms 16452 KB Output is correct
92 Correct 1771 ms 16500 KB Output is correct
93 Correct 2206 ms 16280 KB Output is correct
94 Correct 2289 ms 18968 KB Output is correct
95 Correct 2273 ms 19088 KB Output is correct
96 Correct 2443 ms 18872 KB Output is correct
97 Correct 1169 ms 17592 KB Output is correct
98 Correct 1466 ms 21344 KB Output is correct
99 Correct 2744 ms 20828 KB Output is correct
100 Correct 2829 ms 21100 KB Output is correct
101 Correct 2700 ms 21256 KB Output is correct
102 Correct 2730 ms 21068 KB Output is correct
103 Correct 2659 ms 19496 KB Output is correct
104 Correct 2625 ms 19440 KB Output is correct
105 Correct 2096 ms 21188 KB Output is correct
106 Correct 1709 ms 20784 KB Output is correct
107 Correct 1821 ms 17468 KB Output is correct
108 Correct 2689 ms 20584 KB Output is correct
109 Correct 2076 ms 18064 KB Output is correct