oj.uz

Submission #258358

# Submission time Handle Problem Language Result Execution time Memory
258358 2020-08-05T19:32:29 Z DS007 Bridges (APIO19_bridges) C++14
100 / 100
 2930 ms 68428 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N = 5e4 + 5, M = 1e5, Q = 1e5, BS = 750;

int sz[N], par[N];
stack<int> s;

void reset() {
    iota(par, par + N, 0);
    fill(sz, sz + N, 1);
}

int find(int x) {
    if (x == par[x])
        return x;
    return find(par[x]);
}

void merge(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py)
        return;

    if (sz[px] < sz[py])
        swap(px, py);

    sz[px] += sz[py];
    par[py] = px;
    s.push(py);
}

void rollback(int x) {
    while (s.size() > x) {
        int temp = s.top();
        s.pop();
        sz[par[temp]] -= sz[temp];
        par[temp] = temp;
    }
}

int u[M], v[M], d[M], t[Q], x[Q], y[Q], ans[Q], n, m, q;

int solveTestCase() {
    cin >> n >> m;
    for (int i = 0; i < m; i++)
        cin >> u[i] >> v[i] >> d[i];

    cin >> q;
    for (int i = 0; i < q; i++)
        cin >> t[i] >> x[i] >> y[i];

    for (int i = 0; i < q; i++) {
        if (t[i] == 1)
            x[i]--;
    }

    for (int i = 0; i < q; i += BS) {
        int l = i, r = min(q - 1, i + BS - 1);
        bool changed[m] = {};

        vector<int> unchanged, updates, ask;
        for (int j = l; j <= r; j++) {
            if (t[j] == 1)
                changed[x[j]] = true, updates.push_back(x[j]);
            else
                ask.push_back(j);
        }

        for (int i = 0; i < m; i++) {
            if (!changed[i])
                unchanged.push_back(i);
        }

        vector<int> join[BS];
        for (int j = l; j <= r; j++) {
            if (t[j] == 1) {
                d[x[j]] = y[j];
            } else {
                for (int k : updates) {
                    if (d[k] >= y[j])
                        join[j - l].push_back(k);
                }
            }
        }

        sort(unchanged.begin(), unchanged.end(), [&](auto a, auto b) {
            return d[a] > d[b];
        });

        sort(ask.begin(), ask.end(), [&](auto a, auto b) {
            return y[a] > y[b];
        });

        reset();
        int ptr = 0;
        for (int j : ask) {
            while (ptr != unchanged.size() && d[unchanged[ptr]] >= y[j])
                merge(u[unchanged[ptr]], v[unchanged[ptr]]), ptr++;

            int temp = s.size();
            for (int k : join[j - l])
                merge(u[k], v[k]);

            ans[j] = sz[find(x[j])];
            rollback(temp);
        }
    }

    for (int i = 0; i < q; i++) {
        if (t[i] == 2)
            cout << ans[i] << " \n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t = 1;
    //cin >> t;
    while (t--)
        solveTestCase();
}

Compilation message

bridges.cpp: In function 'void rollback(long long int)':
bridges.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (s.size() > x) {
            ~~~~~~~~~^~~
bridges.cpp: In function 'long long int solveTestCase()':
bridges.cpp:99:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while (ptr != unchanged.size() && d[unchanged[ptr]] >= y[j])
                    ~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:115:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 33 ms 2592 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 45 ms 2636 KB Output is correct
6 Correct 34 ms 2560 KB Output is correct
7 Correct 43 ms 2572 KB Output is correct
8 Correct 40 ms 2432 KB Output is correct
9 Correct 57 ms 3084 KB Output is correct
10 Correct 41 ms 2488 KB Output is correct
11 Correct 43 ms 2532 KB Output is correct
12 Correct 50 ms 2856 KB Output is correct
13 Correct 44 ms 2568 KB Output is correct
14 Correct 40 ms 2608 KB Output is correct
15 Correct 41 ms 2616 KB Output is correct
16 Correct 45 ms 2788 KB Output is correct
17 Correct 44 ms 2740 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 62172 KB Output is correct
2 Correct 1711 ms 62464 KB Output is correct
3 Correct 1730 ms 62224 KB Output is correct
4 Correct 1730 ms 62380 KB Output is correct
5 Correct 1709 ms 62372 KB Output is correct
6 Correct 2273 ms 63012 KB Output is correct
7 Correct 2275 ms 63152 KB Output is correct
8 Correct 2284 ms 63032 KB Output is correct
9 Correct 53 ms 5240 KB Output is correct
10 Correct 1199 ms 62788 KB Output is correct
11 Correct 1167 ms 63636 KB Output is correct
12 Correct 1532 ms 62732 KB Output is correct
13 Correct 1521 ms 61592 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 42716 KB Output is correct
2 Correct 861 ms 15652 KB Output is correct
3 Correct 1519 ms 43444 KB Output is correct
4 Correct 1292 ms 43028 KB Output is correct
5 Correct 53 ms 5240 KB Output is correct
6 Correct 1477 ms 43748 KB Output is correct
7 Correct 1171 ms 42716 KB Output is correct
8 Correct 1055 ms 42180 KB Output is correct
9 Correct 936 ms 42640 KB Output is correct
10 Correct 871 ms 42464 KB Output is correct
11 Correct 932 ms 41656 KB Output is correct
12 Correct 880 ms 41320 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2350 ms 63316 KB Output is correct
2 Correct 51 ms 6008 KB Output is correct
3 Correct 242 ms 7644 KB Output is correct
4 Correct 111 ms 7772 KB Output is correct
5 Correct 1163 ms 65216 KB Output is correct
6 Correct 2201 ms 66532 KB Output is correct
7 Correct 1169 ms 64952 KB Output is correct
8 Correct 1164 ms 64176 KB Output is correct
9 Correct 1154 ms 64056 KB Output is correct
10 Correct 1133 ms 64060 KB Output is correct
11 Correct 1696 ms 65936 KB Output is correct
12 Correct 1671 ms 66076 KB Output is correct
13 Correct 1746 ms 65984 KB Output is correct
14 Correct 1044 ms 65004 KB Output is correct
15 Correct 1163 ms 65060 KB Output is correct
16 Correct 2249 ms 67204 KB Output is correct
17 Correct 2295 ms 67084 KB Output is correct
18 Correct 2325 ms 67568 KB Output is correct
19 Correct 2283 ms 67500 KB Output is correct
20 Correct 1903 ms 66516 KB Output is correct
21 Correct 1895 ms 66640 KB Output is correct
22 Correct 2169 ms 65840 KB Output is correct
23 Correct 1299 ms 59440 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1784 ms 62172 KB Output is correct
2 Correct 1711 ms 62464 KB Output is correct
3 Correct 1730 ms 62224 KB Output is correct
4 Correct 1730 ms 62380 KB Output is correct
5 Correct 1709 ms 62372 KB Output is correct
6 Correct 2273 ms 63012 KB Output is correct
7 Correct 2275 ms 63152 KB Output is correct
8 Correct 2284 ms 63032 KB Output is correct
9 Correct 53 ms 5240 KB Output is correct
10 Correct 1199 ms 62788 KB Output is correct
11 Correct 1167 ms 63636 KB Output is correct
12 Correct 1532 ms 62732 KB Output is correct
13 Correct 1521 ms 61592 KB Output is correct
14 Correct 1278 ms 42716 KB Output is correct
15 Correct 861 ms 15652 KB Output is correct
16 Correct 1519 ms 43444 KB Output is correct
17 Correct 1292 ms 43028 KB Output is correct
18 Correct 53 ms 5240 KB Output is correct
19 Correct 1477 ms 43748 KB Output is correct
20 Correct 1171 ms 42716 KB Output is correct
21 Correct 1055 ms 42180 KB Output is correct
22 Correct 936 ms 42640 KB Output is correct
23 Correct 871 ms 42464 KB Output is correct
24 Correct 932 ms 41656 KB Output is correct
25 Correct 880 ms 41320 KB Output is correct
26 Correct 1730 ms 62404 KB Output is correct
27 Correct 2056 ms 63092 KB Output is correct
28 Correct 1798 ms 62388 KB Output is correct
29 Correct 1432 ms 61496 KB Output is correct
30 Correct 1997 ms 62872 KB Output is correct
31 Correct 2033 ms 62956 KB Output is correct
32 Correct 2024 ms 63020 KB Output is correct
33 Correct 1818 ms 62172 KB Output is correct
34 Correct 1878 ms 62284 KB Output is correct
35 Correct 1795 ms 62448 KB Output is correct
36 Correct 1449 ms 61476 KB Output is correct
37 Correct 1461 ms 61556 KB Output is correct
38 Correct 1426 ms 61328 KB Output is correct
39 Correct 1318 ms 61688 KB Output is correct
40 Correct 1266 ms 61700 KB Output is correct
41 Correct 1264 ms 61812 KB Output is correct
42 Correct 1228 ms 59056 KB Output is correct
43 Correct 1218 ms 59064 KB Output is correct
44 Correct 1224 ms 58628 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 33 ms 2592 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 45 ms 2636 KB Output is correct
6 Correct 34 ms 2560 KB Output is correct
7 Correct 43 ms 2572 KB Output is correct
8 Correct 40 ms 2432 KB Output is correct
9 Correct 57 ms 3084 KB Output is correct
10 Correct 41 ms 2488 KB Output is correct
11 Correct 43 ms 2532 KB Output is correct
12 Correct 50 ms 2856 KB Output is correct
13 Correct 44 ms 2568 KB Output is correct
14 Correct 40 ms 2608 KB Output is correct
15 Correct 41 ms 2616 KB Output is correct
16 Correct 45 ms 2788 KB Output is correct
17 Correct 44 ms 2740 KB Output is correct
18 Correct 1784 ms 62172 KB Output is correct
19 Correct 1711 ms 62464 KB Output is correct
20 Correct 1730 ms 62224 KB Output is correct
21 Correct 1730 ms 62380 KB Output is correct
22 Correct 1709 ms 62372 KB Output is correct
23 Correct 2273 ms 63012 KB Output is correct
24 Correct 2275 ms 63152 KB Output is correct
25 Correct 2284 ms 63032 KB Output is correct
26 Correct 53 ms 5240 KB Output is correct
27 Correct 1199 ms 62788 KB Output is correct
28 Correct 1167 ms 63636 KB Output is correct
29 Correct 1532 ms 62732 KB Output is correct
30 Correct 1521 ms 61592 KB Output is correct
31 Correct 1278 ms 42716 KB Output is correct
32 Correct 861 ms 15652 KB Output is correct
33 Correct 1519 ms 43444 KB Output is correct
34 Correct 1292 ms 43028 KB Output is correct
35 Correct 53 ms 5240 KB Output is correct
36 Correct 1477 ms 43748 KB Output is correct
37 Correct 1171 ms 42716 KB Output is correct
38 Correct 1055 ms 42180 KB Output is correct
39 Correct 936 ms 42640 KB Output is correct
40 Correct 871 ms 42464 KB Output is correct
41 Correct 932 ms 41656 KB Output is correct
42 Correct 880 ms 41320 KB Output is correct
43 Correct 2350 ms 63316 KB Output is correct
44 Correct 51 ms 6008 KB Output is correct
45 Correct 242 ms 7644 KB Output is correct
46 Correct 111 ms 7772 KB Output is correct
47 Correct 1163 ms 65216 KB Output is correct
48 Correct 2201 ms 66532 KB Output is correct
49 Correct 1169 ms 64952 KB Output is correct
50 Correct 1164 ms 64176 KB Output is correct
51 Correct 1154 ms 64056 KB Output is correct
52 Correct 1133 ms 64060 KB Output is correct
53 Correct 1696 ms 65936 KB Output is correct
54 Correct 1671 ms 66076 KB Output is correct
55 Correct 1746 ms 65984 KB Output is correct
56 Correct 1044 ms 65004 KB Output is correct
57 Correct 1163 ms 65060 KB Output is correct
58 Correct 2249 ms 67204 KB Output is correct
59 Correct 2295 ms 67084 KB Output is correct
60 Correct 2325 ms 67568 KB Output is correct
61 Correct 2283 ms 67500 KB Output is correct
62 Correct 1903 ms 66516 KB Output is correct
63 Correct 1895 ms 66640 KB Output is correct
64 Correct 2169 ms 65840 KB Output is correct
65 Correct 1299 ms 59440 KB Output is correct
66 Correct 1730 ms 62404 KB Output is correct
67 Correct 2056 ms 63092 KB Output is correct
68 Correct 1798 ms 62388 KB Output is correct
69 Correct 1432 ms 61496 KB Output is correct
70 Correct 1997 ms 62872 KB Output is correct
71 Correct 2033 ms 62956 KB Output is correct
72 Correct 2024 ms 63020 KB Output is correct
73 Correct 1818 ms 62172 KB Output is correct
74 Correct 1878 ms 62284 KB Output is correct
75 Correct 1795 ms 62448 KB Output is correct
76 Correct 1449 ms 61476 KB Output is correct
77 Correct 1461 ms 61556 KB Output is correct
78 Correct 1426 ms 61328 KB Output is correct
79 Correct 1318 ms 61688 KB Output is correct
80 Correct 1266 ms 61700 KB Output is correct
81 Correct 1264 ms 61812 KB Output is correct
82 Correct 1228 ms 59056 KB Output is correct
83 Correct 1218 ms 59064 KB Output is correct
84 Correct 1224 ms 58628 KB Output is correct
85 Correct 2758 ms 66936 KB Output is correct
86 Correct 250 ms 8408 KB Output is correct
87 Correct 130 ms 8600 KB Output is correct
88 Correct 1569 ms 65844 KB Output is correct
89 Correct 2692 ms 67096 KB Output is correct
90 Correct 1611 ms 65852 KB Output is correct
91 Correct 1870 ms 64352 KB Output is correct
92 Correct 1831 ms 64568 KB Output is correct
93 Correct 2385 ms 65140 KB Output is correct
94 Correct 2245 ms 66972 KB Output is correct
95 Correct 2347 ms 67296 KB Output is correct
96 Correct 2388 ms 67400 KB Output is correct
97 Correct 1396 ms 65492 KB Output is correct
98 Correct 1324 ms 65124 KB Output is correct
99 Correct 2778 ms 67664 KB Output is correct
100 Correct 2711 ms 67752 KB Output is correct
101 Correct 2883 ms 68368 KB Output is correct
102 Correct 2930 ms 68428 KB Output is correct
103 Correct 2747 ms 67952 KB Output is correct
104 Correct 2647 ms 68060 KB Output is correct
105 Correct 2173 ms 66772 KB Output is correct
106 Correct 1846 ms 65712 KB Output is correct
107 Correct 2149 ms 66868 KB Output is correct
108 Correct 2665 ms 67604 KB Output is correct
109 Correct 1831 ms 60996 KB Output is correct