oj.uz

Submission #622768

# Submission time Handle Problem Language Result Execution time Memory
622768 2022-08-04T14:17:20 Z Do_you_copy Bridges (APIO19_bridges) C++17
100 / 100
 2244 ms 16396 KB 
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 2e5 + 10;
const int maxM = 2e5 + 10;
const int maxQ = 2e5 + 10;
const int SQRT = 1000;
int n, m, q;

struct TEdge{
    int u, v, w, idx;
};
TEdge e[maxM];

struct TQuery{
    int t, x, y;
};

TQuery query[maxQ];
struct TDSU{
    vector <pii> save;
    vector <int> lab;
    TDSU(){}
    TDSU(int _n){
        lab.resize(_n, -1);
    }
    inline void resize(int _n){
        lab.resize(_n, -1);
    }
    inline int find_set(int u){
        if (lab[u] < 0) return u;
        return lab[u] = find_set(lab[u]);
    }
    inline int find(int u){
        if (lab[u] < 0) return u;
        return find(lab[u]);
    }
    inline void merge(int u, int v){
        if (lab[u] > lab[v]) swap(u, v);
        save.pb({v, lab[v]});
        lab[u] += lab[v];
        lab[v] = u;
    }
    inline void undo(){

        int v = save.back().fi;
        int u = lab[v];
        lab[v] = save.back().se;
        lab[u] -= lab[v];
        save.pop_back();
    }
    inline void clear(){
        lab.clear();
        save.clear();
    }
    inline void reset(int _n){
        clear();
        resize(_n);
    }
    inline void roll_back(int _n){
        while (save.size() > _n) undo();
    }
};

TDSU dsu;

bool changed[maxM];
int ans[maxQ];
vector <int> join[maxQ];
void Init(){
    cin >> n >> m;
    for (int i = 1; i <= m; ++i){
        cin >> e[i].u >> e[i].v >> e[i].w;
        e[i].idx = i;
    }
    vector <int> block_idx;
    ll cnt = 0;
    block_idx.pb(0);
    cin >> q;
    for (int i = 1; i <= q; ++i){
        cin >> query[i].t >> query[i].x >> query[i].y;
        --query[i].t;
        ++cnt;
        if (cnt >= SQRT){
            block_idx.pb(i);
            cnt = 0;
        }
    }
    block_idx.pb(q);
    //cerr << q << " ";
    for (int _ = 0; _ < block_idx.size() - 1; ++_){
        int l = block_idx[_] + 1, r = block_idx[_ + 1];
        dsu.reset(n + 1);
        vector <int> ask, unchanged, unstable;
        for (int i = l; i <= r; ++i){
            if (query[i].t) ask.pb(i);
            else{
                changed[query[i].x] = 1;
                unstable.pb(i);
            }
        }
        for (int i = 1; i <= m; ++i){
            if (!changed[i]) unchanged.pb(i);
            else changed[i] = 0;
        }
        for (int i = l; i <= r; ++i){
            if (!query[i].t) e[query[i].x].w = query[i].y;
            else{
                join[i - l].clear();
                for (int j: unstable){
                    if (e[query[j].x].w >= query[i].y) join[i - l].pb(query[j].x);
                }
            }
        }
        sort(ask.begin(), ask.end(),[&](const int &i, const int &j){
            return query[i].y > query[j].y;
        });
        sort(unchanged.begin(), unchanged.end(),[&](const int &i, const int &j){
            return e[i].w > e[j].w;
        });
        int j = 0;
        for (int __ = 0; __ < ask.size(); ++__){
            int i = ask[__];
            while (j < unchanged.size() && e[unchanged[j]].w >= query[i].y){
                int x = dsu.find_set(e[unchanged[j]].u), y = dsu.find_set(e[unchanged[j]].v);
                if (x != y){
                    dsu.merge(x, y);
                }
                ++j;
            }
            int prev_sz = dsu.save.size();
            for (int jj: join[i - l]){
                int x = dsu.find(e[jj].u), y = dsu.find(e[jj].v);
                if (x != y){
                    dsu.merge(x, y);
                }
            }
            ans[i] = - dsu.lab[dsu.find(query[i].x)];
            dsu.roll_back(prev_sz);
        }
    }
    for (int i = 1; i <= q; ++i){
        if (query[i].t){
            cout << ans[i] << "\n";
            //cerr << ans[i] << "\n";
        }
    }
}


int main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        freopen(taskname".out", "w", stdout);
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
}

Compilation message

bridges.cpp: In member function 'void TDSU::roll_back(int)':
bridges.cpp:85:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   85 |         while (save.size() > _n) undo();
      |                ~~~~~~~~~~~~^~~~
bridges.cpp: In function 'void Init()':
bridges.cpp:115:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |     for (int _ = 0; _ < block_idx.size() - 1; ++_){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:146:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |         for (int __ = 0; __ < ask.size(); ++__){
      |                          ~~~^~~~~~~~~~~~
bridges.cpp:148:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |             while (j < unchanged.size() && e[unchanged[j]].w >= query[i].y){
      |                    ~~^~~~~~~~~~~~~~~~~~
bridges.cpp: In function 'int main()':
bridges.cpp:177:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:178:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 29 ms 7308 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 48 ms 7536 KB Output is correct
6 Correct 31 ms 7280 KB Output is correct
7 Correct 35 ms 8176 KB Output is correct
8 Correct 45 ms 7232 KB Output is correct
9 Correct 42 ms 8872 KB Output is correct
10 Correct 48 ms 7408 KB Output is correct
11 Correct 46 ms 7268 KB Output is correct
12 Correct 51 ms 7420 KB Output is correct
13 Correct 57 ms 7376 KB Output is correct
14 Correct 47 ms 7408 KB Output is correct
15 Correct 67 ms 7444 KB Output is correct
16 Correct 40 ms 8696 KB Output is correct
17 Correct 50 ms 8068 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 11500 KB Output is correct
2 Correct 1580 ms 11392 KB Output is correct
3 Correct 1317 ms 11372 KB Output is correct
4 Correct 1363 ms 11284 KB Output is correct
5 Correct 1408 ms 11552 KB Output is correct
6 Correct 1927 ms 12828 KB Output is correct
7 Correct 1828 ms 12808 KB Output is correct
8 Correct 1841 ms 12812 KB Output is correct
9 Correct 68 ms 6908 KB Output is correct
10 Correct 1041 ms 12940 KB Output is correct
11 Correct 986 ms 12936 KB Output is correct
12 Correct 1209 ms 9392 KB Output is correct
13 Correct 1135 ms 12724 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1027 ms 10820 KB Output is correct
2 Correct 680 ms 11548 KB Output is correct
3 Correct 1129 ms 12284 KB Output is correct
4 Correct 1002 ms 10768 KB Output is correct
5 Correct 40 ms 6832 KB Output is correct
6 Correct 1067 ms 10728 KB Output is correct
7 Correct 857 ms 10340 KB Output is correct
8 Correct 764 ms 10256 KB Output is correct
9 Correct 716 ms 8740 KB Output is correct
10 Correct 636 ms 8620 KB Output is correct
11 Correct 720 ms 12112 KB Output is correct
12 Correct 613 ms 12180 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1681 ms 9964 KB Output is correct
2 Correct 42 ms 6832 KB Output is correct
3 Correct 191 ms 7752 KB Output is correct
4 Correct 91 ms 7848 KB Output is correct
5 Correct 1051 ms 9792 KB Output is correct
6 Correct 1850 ms 9896 KB Output is correct
7 Correct 795 ms 9752 KB Output is correct
8 Correct 883 ms 8636 KB Output is correct
9 Correct 776 ms 8536 KB Output is correct
10 Correct 825 ms 8784 KB Output is correct
11 Correct 1290 ms 9488 KB Output is correct
12 Correct 1291 ms 9452 KB Output is correct
13 Correct 1433 ms 9540 KB Output is correct
14 Correct 2147 ms 9912 KB Output is correct
15 Correct 850 ms 9912 KB Output is correct
16 Correct 1720 ms 9908 KB Output is correct
17 Correct 1873 ms 9884 KB Output is correct
18 Correct 1709 ms 9852 KB Output is correct
19 Correct 2244 ms 10076 KB Output is correct
20 Correct 1425 ms 9700 KB Output is correct
21 Correct 1372 ms 9652 KB Output is correct
22 Correct 1437 ms 9812 KB Output is correct
23 Correct 911 ms 9440 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1335 ms 11500 KB Output is correct
2 Correct 1580 ms 11392 KB Output is correct
3 Correct 1317 ms 11372 KB Output is correct
4 Correct 1363 ms 11284 KB Output is correct
5 Correct 1408 ms 11552 KB Output is correct
6 Correct 1927 ms 12828 KB Output is correct
7 Correct 1828 ms 12808 KB Output is correct
8 Correct 1841 ms 12812 KB Output is correct
9 Correct 68 ms 6908 KB Output is correct
10 Correct 1041 ms 12940 KB Output is correct
11 Correct 986 ms 12936 KB Output is correct
12 Correct 1209 ms 9392 KB Output is correct
13 Correct 1135 ms 12724 KB Output is correct
14 Correct 1027 ms 10820 KB Output is correct
15 Correct 680 ms 11548 KB Output is correct
16 Correct 1129 ms 12284 KB Output is correct
17 Correct 1002 ms 10768 KB Output is correct
18 Correct 40 ms 6832 KB Output is correct
19 Correct 1067 ms 10728 KB Output is correct
20 Correct 857 ms 10340 KB Output is correct
21 Correct 764 ms 10256 KB Output is correct
22 Correct 716 ms 8740 KB Output is correct
23 Correct 636 ms 8620 KB Output is correct
24 Correct 720 ms 12112 KB Output is correct
25 Correct 613 ms 12180 KB Output is correct
26 Correct 1224 ms 11772 KB Output is correct
27 Correct 1538 ms 13332 KB Output is correct
28 Correct 1490 ms 11684 KB Output is correct
29 Correct 967 ms 11196 KB Output is correct
30 Correct 1447 ms 13124 KB Output is correct
31 Correct 1664 ms 13168 KB Output is correct
32 Correct 1586 ms 13168 KB Output is correct
33 Correct 1472 ms 11548 KB Output is correct
34 Correct 1378 ms 11468 KB Output is correct
35 Correct 1309 ms 11620 KB Output is correct
36 Correct 1250 ms 11260 KB Output is correct
37 Correct 1214 ms 11264 KB Output is correct
38 Correct 970 ms 11336 KB Output is correct
39 Correct 812 ms 9448 KB Output is correct
40 Correct 797 ms 9584 KB Output is correct
41 Correct 781 ms 9468 KB Output is correct
42 Correct 749 ms 12644 KB Output is correct
43 Correct 773 ms 12576 KB Output is correct
44 Correct 765 ms 12608 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 29 ms 7308 KB Output is correct
4 Correct 6 ms 5204 KB Output is correct
5 Correct 48 ms 7536 KB Output is correct
6 Correct 31 ms 7280 KB Output is correct
7 Correct 35 ms 8176 KB Output is correct
8 Correct 45 ms 7232 KB Output is correct
9 Correct 42 ms 8872 KB Output is correct
10 Correct 48 ms 7408 KB Output is correct
11 Correct 46 ms 7268 KB Output is correct
12 Correct 51 ms 7420 KB Output is correct
13 Correct 57 ms 7376 KB Output is correct
14 Correct 47 ms 7408 KB Output is correct
15 Correct 67 ms 7444 KB Output is correct
16 Correct 40 ms 8696 KB Output is correct
17 Correct 50 ms 8068 KB Output is correct
18 Correct 1335 ms 11500 KB Output is correct
19 Correct 1580 ms 11392 KB Output is correct
20 Correct 1317 ms 11372 KB Output is correct
21 Correct 1363 ms 11284 KB Output is correct
22 Correct 1408 ms 11552 KB Output is correct
23 Correct 1927 ms 12828 KB Output is correct
24 Correct 1828 ms 12808 KB Output is correct
25 Correct 1841 ms 12812 KB Output is correct
26 Correct 68 ms 6908 KB Output is correct
27 Correct 1041 ms 12940 KB Output is correct
28 Correct 986 ms 12936 KB Output is correct
29 Correct 1209 ms 9392 KB Output is correct
30 Correct 1135 ms 12724 KB Output is correct
31 Correct 1027 ms 10820 KB Output is correct
32 Correct 680 ms 11548 KB Output is correct
33 Correct 1129 ms 12284 KB Output is correct
34 Correct 1002 ms 10768 KB Output is correct
35 Correct 40 ms 6832 KB Output is correct
36 Correct 1067 ms 10728 KB Output is correct
37 Correct 857 ms 10340 KB Output is correct
38 Correct 764 ms 10256 KB Output is correct
39 Correct 716 ms 8740 KB Output is correct
40 Correct 636 ms 8620 KB Output is correct
41 Correct 720 ms 12112 KB Output is correct
42 Correct 613 ms 12180 KB Output is correct
43 Correct 1681 ms 9964 KB Output is correct
44 Correct 42 ms 6832 KB Output is correct
45 Correct 191 ms 7752 KB Output is correct
46 Correct 91 ms 7848 KB Output is correct
47 Correct 1051 ms 9792 KB Output is correct
48 Correct 1850 ms 9896 KB Output is correct
49 Correct 795 ms 9752 KB Output is correct
50 Correct 883 ms 8636 KB Output is correct
51 Correct 776 ms 8536 KB Output is correct
52 Correct 825 ms 8784 KB Output is correct
53 Correct 1290 ms 9488 KB Output is correct
54 Correct 1291 ms 9452 KB Output is correct
55 Correct 1433 ms 9540 KB Output is correct
56 Correct 2147 ms 9912 KB Output is correct
57 Correct 850 ms 9912 KB Output is correct
58 Correct 1720 ms 9908 KB Output is correct
59 Correct 1873 ms 9884 KB Output is correct
60 Correct 1709 ms 9852 KB Output is correct
61 Correct 2244 ms 10076 KB Output is correct
62 Correct 1425 ms 9700 KB Output is correct
63 Correct 1372 ms 9652 KB Output is correct
64 Correct 1437 ms 9812 KB Output is correct
65 Correct 911 ms 9440 KB Output is correct
66 Correct 1224 ms 11772 KB Output is correct
67 Correct 1538 ms 13332 KB Output is correct
68 Correct 1490 ms 11684 KB Output is correct
69 Correct 967 ms 11196 KB Output is correct
70 Correct 1447 ms 13124 KB Output is correct
71 Correct 1664 ms 13168 KB Output is correct
72 Correct 1586 ms 13168 KB Output is correct
73 Correct 1472 ms 11548 KB Output is correct
74 Correct 1378 ms 11468 KB Output is correct
75 Correct 1309 ms 11620 KB Output is correct
76 Correct 1250 ms 11260 KB Output is correct
77 Correct 1214 ms 11264 KB Output is correct
78 Correct 970 ms 11336 KB Output is correct
79 Correct 812 ms 9448 KB Output is correct
80 Correct 797 ms 9584 KB Output is correct
81 Correct 781 ms 9468 KB Output is correct
82 Correct 749 ms 12644 KB Output is correct
83 Correct 773 ms 12576 KB Output is correct
84 Correct 765 ms 12608 KB Output is correct
85 Correct 1755 ms 13056 KB Output is correct
86 Correct 179 ms 10168 KB Output is correct
87 Correct 86 ms 11476 KB Output is correct
88 Correct 919 ms 14668 KB Output is correct
89 Correct 1742 ms 13152 KB Output is correct
90 Correct 959 ms 14512 KB Output is correct
91 Correct 1237 ms 11820 KB Output is correct
92 Correct 1228 ms 11496 KB Output is correct
93 Correct 1705 ms 13048 KB Output is correct
94 Correct 1559 ms 12512 KB Output is correct
95 Correct 1512 ms 12528 KB Output is correct
96 Correct 1644 ms 13924 KB Output is correct
97 Correct 781 ms 11000 KB Output is correct
98 Correct 781 ms 14612 KB Output is correct
99 Correct 1877 ms 13548 KB Output is correct
100 Correct 1769 ms 12940 KB Output is correct
101 Correct 1858 ms 12932 KB Output is correct
102 Correct 1923 ms 13376 KB Output is correct
103 Correct 1858 ms 14092 KB Output is correct
104 Correct 1901 ms 14000 KB Output is correct
105 Correct 1598 ms 13796 KB Output is correct
106 Correct 1417 ms 16396 KB Output is correct
107 Correct 1557 ms 13116 KB Output is correct
108 Correct 2009 ms 16388 KB Output is correct
109 Correct 1325 ms 15608 KB Output is correct