oj.uz

Submission #965109

# Submission time Handle Problem Language Result Execution time Memory
965109 2024-04-18T06:57:17 Z steveonalex Bridges (APIO19_bridges) C++17
100 / 100
 1703 ms 19744 KB 
#include <bits/stdc++.h>

using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

struct DSU{
    int n;
    vector<int> parent, sz;
    bool flag;
    vector<pair<int, int>> history;

    DSU(int _n){
        n = _n;
        parent.resize(n+1); sz.resize(n+1, 1);
        for(int i= 1; i<=n; ++i) parent[i] = i;
        flag = 0;
    }

    int find_set(int u){
        if (u == parent[u]) return u;
        if (flag) return find_set(parent[u]);
        else return parent[u] = find_set(parent[u]);
    }

    bool same_set(int u, int v){return find_set(u) == find_set(v);}
    bool join_set(int u, int v){
        u = find_set(u), v = find_set(v);
        if (u != v){
            if (sz[u] < sz[v]) swap(u, v);
            parent[v] = u;
            sz[u] += sz[v];
            if (flag) history.push_back({u, v});
            return true;
        }
        return false;
    }

    int get_size(int u){return sz[find_set(u)];}

    void toggle(){flag = !flag;}
    int get_version(){return history.size();}
    void roll_back(int version){
        while(history.size() > version){
            int u = history.back().first, v = history.back().second;
            history.pop_back();
            parent[v] = v;
            sz[u] -= sz[v];
        }
    }
};

const int N = 1e5 + 69;
const int BLOCK = 500;

int n, m;
array<int, 3> edge[N];
array<int, 3> queries[N];
bool check[N];

vector<array<int, 3>> sweep[N * 2];
int ans[N];

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m; cin >> n >> m;
    for(int i = 1; i<=m; ++i) cin >> edge[i][0] >> edge[i][1] >> edge[i][2];

    int q; cin >> q;
    for(int i = 1; i<=q; ++i){
        cin >> queries[i][0] >> queries[i][1] >> queries[i][2];
    }

    vector<int> b;
    for(int i= 1; i<=m; ++i) b.push_back(edge[i][2]);
    for(int i= 1; i<=q; ++i) b.push_back(queries[i][2]);

    remove_dup(b);

    for(int i = 1; i<=m; ++i) edge[i][2] = lower_bound(ALL(b), edge[i][2]) - b.begin();
    for(int i = 1; i<=q; ++i) queries[i][2]= lower_bound(ALL(b), queries[i][2]) - b.begin();

    for(int t= 1; t <= q; t += BLOCK){
        int l = t, r = min(t + BLOCK - 1, q);

        vector<int> ligma;
        for(int i= l; i<=r; ++i){
            if (queries[i][0] == 1 && !check[queries[i][1]]){
                check[queries[i][1]] = true;
                ligma.push_back(queries[i][1]);
            }
        }

        DSU mst(n);
        for(int i = b.size(); i>=0; --i) sweep[i].clear();
        for(int i = 1; i<=m; ++i) if (!check[i]){
            sweep[edge[i][2]].push_back({{0,edge[i][0], edge[i][1]}});
        }

        for(int i = l; i<=r; ++i) if (queries[i][0] == 2){
            sweep[queries[i][2]].push_back({{i,queries[i][1], queries[i][2]}});
        }

        for(int i = b.size(); i>=0; --i){
            for(array<int, 3> j: sweep[i]){
                if (j[0] == 0){
                    mst.join_set(j[1], j[2]);
                }
                else{
                    for(int k: ligma) mst.same_set(edge[k][0], edge[k][1]);
                    mst.toggle();
                    int cur = mst.get_version();
                    for(int k = l; k <= j[0]; ++k){
                        if (queries[k][0] == 1){
                            int e = queries[k][1];
                            swap(edge[e][2], queries[k][2]);
                        }
                    }

                    for(int k: ligma) {
                        if (edge[k][2] >= i) mst.join_set(edge[k][0], edge[k][1]);
                    }

                    ans[j[0]] = mst.get_size(j[1]);
                    mst.roll_back(cur);

                    mst.toggle();

                    for(int k = j[0]; k >= l; --k){
                        if (queries[k][0] == 1){
                            int e = queries[k][1];
                            swap(edge[e][2], queries[k][2]);
                        }
                    }
                }
            }
        }

        for(int i= l; i<=r; ++i){
            if (queries[i][0] == 1){
                int e = queries[i][1];
                check[e] = false;
                edge[e][2] = queries[i][2];
            }
        }
    }

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

    return 0;
}

Compilation message

bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:83:30: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   83 |         while(history.size() > version){
      |               ~~~~~~~~~~~~~~~^~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 23 ms 7000 KB Output is correct
4 Correct 10 ms 7176 KB Output is correct
5 Correct 14 ms 6748 KB Output is correct
6 Correct 13 ms 6748 KB Output is correct
7 Correct 14 ms 6748 KB Output is correct
8 Correct 15 ms 7004 KB Output is correct
9 Correct 17 ms 6748 KB Output is correct
10 Correct 17 ms 6920 KB Output is correct
11 Correct 15 ms 7004 KB Output is correct
12 Correct 21 ms 6892 KB Output is correct
13 Correct 17 ms 6892 KB Output is correct
14 Correct 17 ms 7004 KB Output is correct
15 Correct 16 ms 6972 KB Output is correct
16 Correct 17 ms 6844 KB Output is correct
17 Correct 15 ms 6744 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 990 ms 16104 KB Output is correct
2 Correct 963 ms 15956 KB Output is correct
3 Correct 946 ms 15864 KB Output is correct
4 Correct 947 ms 16268 KB Output is correct
5 Correct 1006 ms 16016 KB Output is correct
6 Correct 990 ms 15116 KB Output is correct
7 Correct 955 ms 12740 KB Output is correct
8 Correct 1101 ms 13192 KB Output is correct
9 Correct 148 ms 10492 KB Output is correct
10 Correct 433 ms 9576 KB Output is correct
11 Correct 398 ms 9676 KB Output is correct
12 Correct 661 ms 12944 KB Output is correct
13 Correct 833 ms 12996 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 678 ms 12156 KB Output is correct
2 Correct 367 ms 9916 KB Output is correct
3 Correct 686 ms 11480 KB Output is correct
4 Correct 662 ms 12292 KB Output is correct
5 Correct 156 ms 10376 KB Output is correct
6 Correct 701 ms 12184 KB Output is correct
7 Correct 657 ms 12296 KB Output is correct
8 Correct 623 ms 12256 KB Output is correct
9 Correct 518 ms 12308 KB Output is correct
10 Correct 546 ms 12272 KB Output is correct
11 Correct 571 ms 11992 KB Output is correct
12 Correct 586 ms 11916 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1436 ms 15948 KB Output is correct
2 Correct 146 ms 11724 KB Output is correct
3 Correct 87 ms 13524 KB Output is correct
4 Correct 53 ms 12068 KB Output is correct
5 Correct 470 ms 13900 KB Output is correct
6 Correct 1217 ms 19600 KB Output is correct
7 Correct 489 ms 13828 KB Output is correct
8 Correct 802 ms 15948 KB Output is correct
9 Correct 736 ms 15876 KB Output is correct
10 Correct 640 ms 15860 KB Output is correct
11 Correct 1111 ms 17432 KB Output is correct
12 Correct 1174 ms 17812 KB Output is correct
13 Correct 855 ms 17680 KB Output is correct
14 Correct 464 ms 13616 KB Output is correct
15 Correct 568 ms 13664 KB Output is correct
16 Correct 1322 ms 19316 KB Output is correct
17 Correct 1450 ms 19388 KB Output is correct
18 Correct 1480 ms 19408 KB Output is correct
19 Correct 1417 ms 19600 KB Output is correct
20 Correct 853 ms 18144 KB Output is correct
21 Correct 919 ms 17980 KB Output is correct
22 Correct 1056 ms 19164 KB Output is correct
23 Correct 569 ms 12788 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 990 ms 16104 KB Output is correct
2 Correct 963 ms 15956 KB Output is correct
3 Correct 946 ms 15864 KB Output is correct
4 Correct 947 ms 16268 KB Output is correct
5 Correct 1006 ms 16016 KB Output is correct
6 Correct 990 ms 15116 KB Output is correct
7 Correct 955 ms 12740 KB Output is correct
8 Correct 1101 ms 13192 KB Output is correct
9 Correct 148 ms 10492 KB Output is correct
10 Correct 433 ms 9576 KB Output is correct
11 Correct 398 ms 9676 KB Output is correct
12 Correct 661 ms 12944 KB Output is correct
13 Correct 833 ms 12996 KB Output is correct
14 Correct 678 ms 12156 KB Output is correct
15 Correct 367 ms 9916 KB Output is correct
16 Correct 686 ms 11480 KB Output is correct
17 Correct 662 ms 12292 KB Output is correct
18 Correct 156 ms 10376 KB Output is correct
19 Correct 701 ms 12184 KB Output is correct
20 Correct 657 ms 12296 KB Output is correct
21 Correct 623 ms 12256 KB Output is correct
22 Correct 518 ms 12308 KB Output is correct
23 Correct 546 ms 12272 KB Output is correct
24 Correct 571 ms 11992 KB Output is correct
25 Correct 586 ms 11916 KB Output is correct
26 Correct 909 ms 14536 KB Output is correct
27 Correct 989 ms 13928 KB Output is correct
28 Correct 927 ms 14588 KB Output is correct
29 Correct 908 ms 14624 KB Output is correct
30 Correct 993 ms 14580 KB Output is correct
31 Correct 1055 ms 14120 KB Output is correct
32 Correct 991 ms 14188 KB Output is correct
33 Correct 1028 ms 14604 KB Output is correct
34 Correct 1026 ms 14584 KB Output is correct
35 Correct 1056 ms 14588 KB Output is correct
36 Correct 912 ms 14648 KB Output is correct
37 Correct 837 ms 14612 KB Output is correct
38 Correct 849 ms 12988 KB Output is correct
39 Correct 772 ms 13112 KB Output is correct
40 Correct 765 ms 13068 KB Output is correct
41 Correct 752 ms 13092 KB Output is correct
42 Correct 737 ms 13008 KB Output is correct
43 Correct 735 ms 12924 KB Output is correct
44 Correct 807 ms 12800 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 23 ms 7000 KB Output is correct
4 Correct 10 ms 7176 KB Output is correct
5 Correct 14 ms 6748 KB Output is correct
6 Correct 13 ms 6748 KB Output is correct
7 Correct 14 ms 6748 KB Output is correct
8 Correct 15 ms 7004 KB Output is correct
9 Correct 17 ms 6748 KB Output is correct
10 Correct 17 ms 6920 KB Output is correct
11 Correct 15 ms 7004 KB Output is correct
12 Correct 21 ms 6892 KB Output is correct
13 Correct 17 ms 6892 KB Output is correct
14 Correct 17 ms 7004 KB Output is correct
15 Correct 16 ms 6972 KB Output is correct
16 Correct 17 ms 6844 KB Output is correct
17 Correct 15 ms 6744 KB Output is correct
18 Correct 990 ms 16104 KB Output is correct
19 Correct 963 ms 15956 KB Output is correct
20 Correct 946 ms 15864 KB Output is correct
21 Correct 947 ms 16268 KB Output is correct
22 Correct 1006 ms 16016 KB Output is correct
23 Correct 990 ms 15116 KB Output is correct
24 Correct 955 ms 12740 KB Output is correct
25 Correct 1101 ms 13192 KB Output is correct
26 Correct 148 ms 10492 KB Output is correct
27 Correct 433 ms 9576 KB Output is correct
28 Correct 398 ms 9676 KB Output is correct
29 Correct 661 ms 12944 KB Output is correct
30 Correct 833 ms 12996 KB Output is correct
31 Correct 678 ms 12156 KB Output is correct
32 Correct 367 ms 9916 KB Output is correct
33 Correct 686 ms 11480 KB Output is correct
34 Correct 662 ms 12292 KB Output is correct
35 Correct 156 ms 10376 KB Output is correct
36 Correct 701 ms 12184 KB Output is correct
37 Correct 657 ms 12296 KB Output is correct
38 Correct 623 ms 12256 KB Output is correct
39 Correct 518 ms 12308 KB Output is correct
40 Correct 546 ms 12272 KB Output is correct
41 Correct 571 ms 11992 KB Output is correct
42 Correct 586 ms 11916 KB Output is correct
43 Correct 1436 ms 15948 KB Output is correct
44 Correct 146 ms 11724 KB Output is correct
45 Correct 87 ms 13524 KB Output is correct
46 Correct 53 ms 12068 KB Output is correct
47 Correct 470 ms 13900 KB Output is correct
48 Correct 1217 ms 19600 KB Output is correct
49 Correct 489 ms 13828 KB Output is correct
50 Correct 802 ms 15948 KB Output is correct
51 Correct 736 ms 15876 KB Output is correct
52 Correct 640 ms 15860 KB Output is correct
53 Correct 1111 ms 17432 KB Output is correct
54 Correct 1174 ms 17812 KB Output is correct
55 Correct 855 ms 17680 KB Output is correct
56 Correct 464 ms 13616 KB Output is correct
57 Correct 568 ms 13664 KB Output is correct
58 Correct 1322 ms 19316 KB Output is correct
59 Correct 1450 ms 19388 KB Output is correct
60 Correct 1480 ms 19408 KB Output is correct
61 Correct 1417 ms 19600 KB Output is correct
62 Correct 853 ms 18144 KB Output is correct
63 Correct 919 ms 17980 KB Output is correct
64 Correct 1056 ms 19164 KB Output is correct
65 Correct 569 ms 12788 KB Output is correct
66 Correct 909 ms 14536 KB Output is correct
67 Correct 989 ms 13928 KB Output is correct
68 Correct 927 ms 14588 KB Output is correct
69 Correct 908 ms 14624 KB Output is correct
70 Correct 993 ms 14580 KB Output is correct
71 Correct 1055 ms 14120 KB Output is correct
72 Correct 991 ms 14188 KB Output is correct
73 Correct 1028 ms 14604 KB Output is correct
74 Correct 1026 ms 14584 KB Output is correct
75 Correct 1056 ms 14588 KB Output is correct
76 Correct 912 ms 14648 KB Output is correct
77 Correct 837 ms 14612 KB Output is correct
78 Correct 849 ms 12988 KB Output is correct
79 Correct 772 ms 13112 KB Output is correct
80 Correct 765 ms 13068 KB Output is correct
81 Correct 752 ms 13092 KB Output is correct
82 Correct 737 ms 13008 KB Output is correct
83 Correct 735 ms 12924 KB Output is correct
84 Correct 807 ms 12800 KB Output is correct
85 Correct 1482 ms 19516 KB Output is correct
86 Correct 107 ms 13556 KB Output is correct
87 Correct 69 ms 12108 KB Output is correct
88 Correct 636 ms 13592 KB Output is correct
89 Correct 1465 ms 19744 KB Output is correct
90 Correct 727 ms 13900 KB Output is correct
91 Correct 927 ms 15748 KB Output is correct
92 Correct 945 ms 15924 KB Output is correct
93 Correct 991 ms 15652 KB Output is correct
94 Correct 1315 ms 17644 KB Output is correct
95 Correct 1255 ms 17752 KB Output is correct
96 Correct 1169 ms 17568 KB Output is correct
97 Correct 621 ms 13628 KB Output is correct
98 Correct 531 ms 13496 KB Output is correct
99 Correct 1561 ms 19216 KB Output is correct
100 Correct 1703 ms 19092 KB Output is correct
101 Correct 1669 ms 19212 KB Output is correct
102 Correct 1675 ms 19308 KB Output is correct
103 Correct 1262 ms 17920 KB Output is correct
104 Correct 1224 ms 18188 KB Output is correct
105 Correct 1201 ms 17904 KB Output is correct
106 Correct 1161 ms 17344 KB Output is correct
107 Correct 982 ms 18340 KB Output is correct
108 Correct 1388 ms 19016 KB Output is correct
109 Correct 693 ms 12544 KB Output is correct