oj.uz

Submission #934562

# Submission time Handle Problem Language Result Execution time Memory
934562 2024-02-27T15:05:40 Z VladaMG98 Bridges (APIO19_bridges) C++17
100 / 100
 2516 ms 13664 KB 
// Problem: B - Bridges
// Contest: Virtual Judge - 2024-02-27 APIO Simulation
// URL: https://vjudge.net/contest/612540#problem/B
// Memory Limit: 512 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define print(A,t) cerr << #A << ": "; copy(all(A),ostream_iterator<t>(cerr," " )); cerr << endl
#define prArr(A,n,t)  cerr << #A << ": "; copy(A,A + n,ostream_iterator<t>(cerr," " )); cerr << endl
#define what_is(x) cerr << #x << " is " << x << endl
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 50010, MAXM = 100010, MAXQ = 100010;

int N, M, Q;
int from[MAXM], to[MAXM], weg[MAXM];
int type[MAXQ], a[MAXQ], b[MAXQ], ans[MAXQ];

struct event {
    int key, index;
    // index > 0 -- it is an edge index
    // index < 0 -- it is a query index
    event() {}
    event (int _key, int _index) : key(_key), index(_index) {}
    bool operator <(const event &other) const {
        if (key == other.key) return index < other.index;
        return key < other.key;
    }
};

struct dsu_rollback {
    vi par, sz;
    stack<int> roll;
    dsu_rollback (int _n) {
        par.resize(_n + 1);
        sz.resize(_n + 1);
        for (int i = 1; i <= _n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
    int get (int x) { while (par[x] != x) x = par[x]; return x; }
    bool unite (int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) return false;
        if (sz[u] > sz[v]) swap(u, v);
        roll.push(u);
        par[u] = par[v];
        sz[v] += sz[u];
        return true;
    }
    void rollback (int wanted) {
        while (sz(roll) > wanted) {
            int k = roll.top(); roll.pop();
            sz[par[k]] -= sz[k];
            par[k] = k;
        }
    }
    int get_size (int u) {
        return sz[get(u)];
    }
};

bool in_current[MAXM];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> from[i] >> to[i] >> weg[i];
    }

    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> type[i] >> a[i] >> b[i];
    }

    set<event> initial_events;
    for (int j = 1; j <= M; j++) {
        initial_events.insert({weg[j], j});
    }

    const int B = 500;
    for (int i = 1; i <= Q; i += B) {
        int l = i, r = min(Q, l + B - 1);
        // we want to process all the queries between l and r

        set<int> current_vec;
        for (int j = l; j <= r; j++) {
            if (type[j] == 1) {
                current_vec.insert(a[j]);
                in_current[a[j]] = true;
            }
        }

        // gathering all previous edges
        vector<event> small_events;

        // gathering all the queries
        for (int j = l; j <= r; j++) {
            if (type[j] == 2) {
                small_events.emplace_back(b[j], -j);
            }
        }
        sort(all(small_events));

        vector<event> all_events; all_events.reserve(sz(initial_events) + sz(small_events));
        merge(all(initial_events), all(small_events), back_inserter(all_events));

        // sorting everything together
        reverse(all(all_events));
        dsu_rollback d(N);

        for (auto ev : all_events) {
            if (ev.index > 0) {
                if (in_current[ev.index]) continue;
                d.unite(from[ev.index], to[ev.index]);
            } else {
                set<int> curr = current_vec;
                // it is a query, so create a small graph
                int prev_size = d.roll.size();
                int query_index = -ev.index;
                for (int j = query_index - 1; j >= l; j--) {
                    if (type[j] == 2) continue;
                    if (curr.count(a[j])) {
                        if (b[j] >= ev.key) {
                            d.unite(from[a[j]], to[a[j]]);
                        }
                        curr.erase(a[j]);
                    }
                }
                for (auto e : curr) {
                    if (weg[e] >= ev.key) d.unite(from[e], to[e]);
                }
                ans[query_index] = d.get_size(a[query_index]);
                d.rollback(prev_size);
            }
        }

        for (int j = l; j <= r; j++) {
            if (type[j] == 1) {
                initial_events.erase({weg[a[j]], a[j]});
                weg[a[j]] = b[j];
                initial_events.insert({weg[a[j]], a[j]});
                in_current[a[j]] = false;
            }
        }
    }

    for (int i = 1; i <= Q; i++) {
        if (type[i] == 2) {
            cout << ans[i] << endl;
        }
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 89 ms 2780 KB Output is correct
4 Correct 18 ms 2816 KB Output is correct
5 Correct 55 ms 2652 KB Output is correct
6 Correct 47 ms 2652 KB Output is correct
7 Correct 53 ms 2652 KB Output is correct
8 Correct 58 ms 2652 KB Output is correct
9 Correct 41 ms 2884 KB Output is correct
10 Correct 56 ms 2652 KB Output is correct
11 Correct 54 ms 2648 KB Output is correct
12 Correct 53 ms 2652 KB Output is correct
13 Correct 64 ms 2712 KB Output is correct
14 Correct 63 ms 2648 KB Output is correct
15 Correct 55 ms 2904 KB Output is correct
16 Correct 44 ms 2652 KB Output is correct
17 Correct 45 ms 2652 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1559 ms 9260 KB Output is correct
2 Correct 1559 ms 9376 KB Output is correct
3 Correct 1646 ms 9176 KB Output is correct
4 Correct 1569 ms 9464 KB Output is correct
5 Correct 1582 ms 9372 KB Output is correct
6 Correct 1815 ms 9228 KB Output is correct
7 Correct 1777 ms 9308 KB Output is correct
8 Correct 1860 ms 9264 KB Output is correct
9 Correct 152 ms 4056 KB Output is correct
10 Correct 1137 ms 7864 KB Output is correct
11 Correct 1201 ms 7852 KB Output is correct
12 Correct 932 ms 9124 KB Output is correct
13 Correct 1099 ms 9400 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1403 ms 7356 KB Output is correct
2 Correct 1042 ms 4940 KB Output is correct
3 Correct 1306 ms 7184 KB Output is correct
4 Correct 1408 ms 7480 KB Output is correct
5 Correct 146 ms 3920 KB Output is correct
6 Correct 1420 ms 7464 KB Output is correct
7 Correct 1387 ms 7528 KB Output is correct
8 Correct 1296 ms 7820 KB Output is correct
9 Correct 692 ms 7484 KB Output is correct
10 Correct 680 ms 7484 KB Output is correct
11 Correct 836 ms 7480 KB Output is correct
12 Correct 811 ms 7508 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1264 ms 13424 KB Output is correct
2 Correct 144 ms 3928 KB Output is correct
3 Correct 185 ms 10416 KB Output is correct
4 Correct 100 ms 10568 KB Output is correct
5 Correct 1008 ms 12052 KB Output is correct
6 Correct 1232 ms 13348 KB Output is correct
7 Correct 972 ms 11800 KB Output is correct
8 Correct 681 ms 8768 KB Output is correct
9 Correct 685 ms 8740 KB Output is correct
10 Correct 734 ms 8480 KB Output is correct
11 Correct 1040 ms 10556 KB Output is correct
12 Correct 1044 ms 10924 KB Output is correct
13 Correct 1060 ms 10552 KB Output is correct
14 Correct 882 ms 11880 KB Output is correct
15 Correct 964 ms 11832 KB Output is correct
16 Correct 1316 ms 12732 KB Output is correct
17 Correct 1314 ms 12616 KB Output is correct
18 Correct 1363 ms 12904 KB Output is correct
19 Correct 1354 ms 12792 KB Output is correct
20 Correct 1117 ms 11572 KB Output is correct
21 Correct 1133 ms 11596 KB Output is correct
22 Correct 1301 ms 12520 KB Output is correct
23 Correct 978 ms 10528 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1559 ms 9260 KB Output is correct
2 Correct 1559 ms 9376 KB Output is correct
3 Correct 1646 ms 9176 KB Output is correct
4 Correct 1569 ms 9464 KB Output is correct
5 Correct 1582 ms 9372 KB Output is correct
6 Correct 1815 ms 9228 KB Output is correct
7 Correct 1777 ms 9308 KB Output is correct
8 Correct 1860 ms 9264 KB Output is correct
9 Correct 152 ms 4056 KB Output is correct
10 Correct 1137 ms 7864 KB Output is correct
11 Correct 1201 ms 7852 KB Output is correct
12 Correct 932 ms 9124 KB Output is correct
13 Correct 1099 ms 9400 KB Output is correct
14 Correct 1403 ms 7356 KB Output is correct
15 Correct 1042 ms 4940 KB Output is correct
16 Correct 1306 ms 7184 KB Output is correct
17 Correct 1408 ms 7480 KB Output is correct
18 Correct 146 ms 3920 KB Output is correct
19 Correct 1420 ms 7464 KB Output is correct
20 Correct 1387 ms 7528 KB Output is correct
21 Correct 1296 ms 7820 KB Output is correct
22 Correct 692 ms 7484 KB Output is correct
23 Correct 680 ms 7484 KB Output is correct
24 Correct 836 ms 7480 KB Output is correct
25 Correct 811 ms 7508 KB Output is correct
26 Correct 1653 ms 9168 KB Output is correct
27 Correct 1617 ms 8824 KB Output is correct
28 Correct 1693 ms 9228 KB Output is correct
29 Correct 1498 ms 9708 KB Output is correct
30 Correct 1703 ms 8852 KB Output is correct
31 Correct 1692 ms 9040 KB Output is correct
32 Correct 1818 ms 8868 KB Output is correct
33 Correct 1753 ms 9192 KB Output is correct
34 Correct 1847 ms 9264 KB Output is correct
35 Correct 1733 ms 9492 KB Output is correct
36 Correct 1539 ms 8968 KB Output is correct
37 Correct 1584 ms 9144 KB Output is correct
38 Correct 1545 ms 8952 KB Output is correct
39 Correct 986 ms 8948 KB Output is correct
40 Correct 952 ms 8984 KB Output is correct
41 Correct 930 ms 9020 KB Output is correct
42 Correct 999 ms 9144 KB Output is correct
43 Correct 1051 ms 8948 KB Output is correct
44 Correct 1012 ms 9136 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 89 ms 2780 KB Output is correct
4 Correct 18 ms 2816 KB Output is correct
5 Correct 55 ms 2652 KB Output is correct
6 Correct 47 ms 2652 KB Output is correct
7 Correct 53 ms 2652 KB Output is correct
8 Correct 58 ms 2652 KB Output is correct
9 Correct 41 ms 2884 KB Output is correct
10 Correct 56 ms 2652 KB Output is correct
11 Correct 54 ms 2648 KB Output is correct
12 Correct 53 ms 2652 KB Output is correct
13 Correct 64 ms 2712 KB Output is correct
14 Correct 63 ms 2648 KB Output is correct
15 Correct 55 ms 2904 KB Output is correct
16 Correct 44 ms 2652 KB Output is correct
17 Correct 45 ms 2652 KB Output is correct
18 Correct 1559 ms 9260 KB Output is correct
19 Correct 1559 ms 9376 KB Output is correct
20 Correct 1646 ms 9176 KB Output is correct
21 Correct 1569 ms 9464 KB Output is correct
22 Correct 1582 ms 9372 KB Output is correct
23 Correct 1815 ms 9228 KB Output is correct
24 Correct 1777 ms 9308 KB Output is correct
25 Correct 1860 ms 9264 KB Output is correct
26 Correct 152 ms 4056 KB Output is correct
27 Correct 1137 ms 7864 KB Output is correct
28 Correct 1201 ms 7852 KB Output is correct
29 Correct 932 ms 9124 KB Output is correct
30 Correct 1099 ms 9400 KB Output is correct
31 Correct 1403 ms 7356 KB Output is correct
32 Correct 1042 ms 4940 KB Output is correct
33 Correct 1306 ms 7184 KB Output is correct
34 Correct 1408 ms 7480 KB Output is correct
35 Correct 146 ms 3920 KB Output is correct
36 Correct 1420 ms 7464 KB Output is correct
37 Correct 1387 ms 7528 KB Output is correct
38 Correct 1296 ms 7820 KB Output is correct
39 Correct 692 ms 7484 KB Output is correct
40 Correct 680 ms 7484 KB Output is correct
41 Correct 836 ms 7480 KB Output is correct
42 Correct 811 ms 7508 KB Output is correct
43 Correct 1264 ms 13424 KB Output is correct
44 Correct 144 ms 3928 KB Output is correct
45 Correct 185 ms 10416 KB Output is correct
46 Correct 100 ms 10568 KB Output is correct
47 Correct 1008 ms 12052 KB Output is correct
48 Correct 1232 ms 13348 KB Output is correct
49 Correct 972 ms 11800 KB Output is correct
50 Correct 681 ms 8768 KB Output is correct
51 Correct 685 ms 8740 KB Output is correct
52 Correct 734 ms 8480 KB Output is correct
53 Correct 1040 ms 10556 KB Output is correct
54 Correct 1044 ms 10924 KB Output is correct
55 Correct 1060 ms 10552 KB Output is correct
56 Correct 882 ms 11880 KB Output is correct
57 Correct 964 ms 11832 KB Output is correct
58 Correct 1316 ms 12732 KB Output is correct
59 Correct 1314 ms 12616 KB Output is correct
60 Correct 1363 ms 12904 KB Output is correct
61 Correct 1354 ms 12792 KB Output is correct
62 Correct 1117 ms 11572 KB Output is correct
63 Correct 1133 ms 11596 KB Output is correct
64 Correct 1301 ms 12520 KB Output is correct
65 Correct 978 ms 10528 KB Output is correct
66 Correct 1653 ms 9168 KB Output is correct
67 Correct 1617 ms 8824 KB Output is correct
68 Correct 1693 ms 9228 KB Output is correct
69 Correct 1498 ms 9708 KB Output is correct
70 Correct 1703 ms 8852 KB Output is correct
71 Correct 1692 ms 9040 KB Output is correct
72 Correct 1818 ms 8868 KB Output is correct
73 Correct 1753 ms 9192 KB Output is correct
74 Correct 1847 ms 9264 KB Output is correct
75 Correct 1733 ms 9492 KB Output is correct
76 Correct 1539 ms 8968 KB Output is correct
77 Correct 1584 ms 9144 KB Output is correct
78 Correct 1545 ms 8952 KB Output is correct
79 Correct 986 ms 8948 KB Output is correct
80 Correct 952 ms 8984 KB Output is correct
81 Correct 930 ms 9020 KB Output is correct
82 Correct 999 ms 9144 KB Output is correct
83 Correct 1051 ms 8948 KB Output is correct
84 Correct 1012 ms 9136 KB Output is correct
85 Correct 2432 ms 13492 KB Output is correct
86 Correct 239 ms 11328 KB Output is correct
87 Correct 172 ms 11476 KB Output is correct
88 Correct 1862 ms 11748 KB Output is correct
89 Correct 2431 ms 13308 KB Output is correct
90 Correct 1831 ms 11892 KB Output is correct
91 Correct 1688 ms 9164 KB Output is correct
92 Correct 1749 ms 9020 KB Output is correct
93 Correct 1888 ms 8840 KB Output is correct
94 Correct 2144 ms 11164 KB Output is correct
95 Correct 2067 ms 11144 KB Output is correct
96 Correct 2240 ms 11084 KB Output is correct
97 Correct 1288 ms 12412 KB Output is correct
98 Correct 1445 ms 11864 KB Output is correct
99 Correct 2510 ms 13284 KB Output is correct
100 Correct 2516 ms 13392 KB Output is correct
101 Correct 2436 ms 13244 KB Output is correct
102 Correct 2485 ms 13664 KB Output is correct
103 Correct 2393 ms 11816 KB Output is correct
104 Correct 2381 ms 12176 KB Output is correct
105 Correct 1620 ms 11936 KB Output is correct
106 Correct 1225 ms 11376 KB Output is correct
107 Correct 1443 ms 12352 KB Output is correct
108 Correct 2368 ms 13232 KB Output is correct
109 Correct 1894 ms 10400 KB Output is correct