oj.uz

Submission #965108

# Submission time Handle Problem Language Result Execution time Memory
965108 2024-04-18T06:57:02 Z steveonalex Bridges (APIO19_bridges) C++17
59 / 100
 3000 ms 18916 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 = 200;

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 3 ms 6628 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 15 ms 7184 KB Output is correct
4 Correct 8 ms 7000 KB Output is correct
5 Correct 11 ms 7004 KB Output is correct
6 Correct 9 ms 6748 KB Output is correct
7 Correct 9 ms 6748 KB Output is correct
8 Correct 12 ms 7004 KB Output is correct
9 Correct 11 ms 6748 KB Output is correct
10 Correct 12 ms 6992 KB Output is correct
11 Correct 16 ms 7004 KB Output is correct
12 Correct 12 ms 7004 KB Output is correct
13 Correct 14 ms 7000 KB Output is correct
14 Correct 14 ms 7008 KB Output is correct
15 Correct 13 ms 7004 KB Output is correct
16 Correct 9 ms 6748 KB Output is correct
17 Correct 10 ms 6748 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1662 ms 15816 KB Output is correct
2 Correct 1660 ms 15852 KB Output is correct
3 Correct 1582 ms 15908 KB Output is correct
4 Correct 1648 ms 15716 KB Output is correct
5 Correct 1629 ms 15736 KB Output is correct
6 Correct 1615 ms 15188 KB Output is correct
7 Correct 1697 ms 15456 KB Output is correct
8 Correct 1682 ms 15704 KB Output is correct
9 Correct 274 ms 11732 KB Output is correct
10 Correct 620 ms 10952 KB Output is correct
11 Correct 465 ms 11192 KB Output is correct
12 Correct 1227 ms 15260 KB Output is correct
13 Correct 1617 ms 15928 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1132 ms 14584 KB Output is correct
2 Correct 427 ms 11552 KB Output is correct
3 Correct 1053 ms 13632 KB Output is correct
4 Correct 1148 ms 14528 KB Output is correct
5 Correct 222 ms 11860 KB Output is correct
6 Correct 1060 ms 14412 KB Output is correct
7 Correct 1159 ms 14556 KB Output is correct
8 Correct 1044 ms 14476 KB Output is correct
9 Correct 912 ms 14724 KB Output is correct
10 Correct 1004 ms 14604 KB Output is correct
11 Correct 1064 ms 14356 KB Output is correct
12 Correct 1143 ms 14272 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3015 ms 18916 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1662 ms 15816 KB Output is correct
2 Correct 1660 ms 15852 KB Output is correct
3 Correct 1582 ms 15908 KB Output is correct
4 Correct 1648 ms 15716 KB Output is correct
5 Correct 1629 ms 15736 KB Output is correct
6 Correct 1615 ms 15188 KB Output is correct
7 Correct 1697 ms 15456 KB Output is correct
8 Correct 1682 ms 15704 KB Output is correct
9 Correct 274 ms 11732 KB Output is correct
10 Correct 620 ms 10952 KB Output is correct
11 Correct 465 ms 11192 KB Output is correct
12 Correct 1227 ms 15260 KB Output is correct
13 Correct 1617 ms 15928 KB Output is correct
14 Correct 1132 ms 14584 KB Output is correct
15 Correct 427 ms 11552 KB Output is correct
16 Correct 1053 ms 13632 KB Output is correct
17 Correct 1148 ms 14528 KB Output is correct
18 Correct 222 ms 11860 KB Output is correct
19 Correct 1060 ms 14412 KB Output is correct
20 Correct 1159 ms 14556 KB Output is correct
21 Correct 1044 ms 14476 KB Output is correct
22 Correct 912 ms 14724 KB Output is correct
23 Correct 1004 ms 14604 KB Output is correct
24 Correct 1064 ms 14356 KB Output is correct
25 Correct 1143 ms 14272 KB Output is correct
26 Correct 1579 ms 15812 KB Output is correct
27 Correct 1715 ms 14976 KB Output is correct
28 Correct 1760 ms 15928 KB Output is correct
29 Correct 1819 ms 15708 KB Output is correct
30 Correct 1797 ms 15352 KB Output is correct
31 Correct 1765 ms 15268 KB Output is correct
32 Correct 1752 ms 15244 KB Output is correct
33 Correct 1768 ms 15804 KB Output is correct
34 Correct 1813 ms 15824 KB Output is correct
35 Correct 1744 ms 15744 KB Output is correct
36 Correct 1714 ms 15804 KB Output is correct
37 Correct 1811 ms 15792 KB Output is correct
38 Correct 1822 ms 15816 KB Output is correct
39 Correct 1582 ms 15996 KB Output is correct
40 Correct 1595 ms 15856 KB Output is correct
41 Correct 1542 ms 15892 KB Output is correct
42 Correct 1596 ms 15680 KB Output is correct
43 Correct 1857 ms 15836 KB Output is correct
44 Correct 1736 ms 15652 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6628 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 15 ms 7184 KB Output is correct
4 Correct 8 ms 7000 KB Output is correct
5 Correct 11 ms 7004 KB Output is correct
6 Correct 9 ms 6748 KB Output is correct
7 Correct 9 ms 6748 KB Output is correct
8 Correct 12 ms 7004 KB Output is correct
9 Correct 11 ms 6748 KB Output is correct
10 Correct 12 ms 6992 KB Output is correct
11 Correct 16 ms 7004 KB Output is correct
12 Correct 12 ms 7004 KB Output is correct
13 Correct 14 ms 7000 KB Output is correct
14 Correct 14 ms 7008 KB Output is correct
15 Correct 13 ms 7004 KB Output is correct
16 Correct 9 ms 6748 KB Output is correct
17 Correct 10 ms 6748 KB Output is correct
18 Correct 1662 ms 15816 KB Output is correct
19 Correct 1660 ms 15852 KB Output is correct
20 Correct 1582 ms 15908 KB Output is correct
21 Correct 1648 ms 15716 KB Output is correct
22 Correct 1629 ms 15736 KB Output is correct
23 Correct 1615 ms 15188 KB Output is correct
24 Correct 1697 ms 15456 KB Output is correct
25 Correct 1682 ms 15704 KB Output is correct
26 Correct 274 ms 11732 KB Output is correct
27 Correct 620 ms 10952 KB Output is correct
28 Correct 465 ms 11192 KB Output is correct
29 Correct 1227 ms 15260 KB Output is correct
30 Correct 1617 ms 15928 KB Output is correct
31 Correct 1132 ms 14584 KB Output is correct
32 Correct 427 ms 11552 KB Output is correct
33 Correct 1053 ms 13632 KB Output is correct
34 Correct 1148 ms 14528 KB Output is correct
35 Correct 222 ms 11860 KB Output is correct
36 Correct 1060 ms 14412 KB Output is correct
37 Correct 1159 ms 14556 KB Output is correct
38 Correct 1044 ms 14476 KB Output is correct
39 Correct 912 ms 14724 KB Output is correct
40 Correct 1004 ms 14604 KB Output is correct
41 Correct 1064 ms 14356 KB Output is correct
42 Correct 1143 ms 14272 KB Output is correct
43 Execution timed out 3015 ms 18916 KB Time limit exceeded
44 Halted 0 ms 0 KB -