oj.uz

Submission #851080

# Submission time Handle Problem Language Result Execution time Memory
851080 2023-09-18T13:29:19 Z nonono Bridges (APIO19_bridges) C++14
100 / 100
 1627 ms 12992 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int mxN = 1e5 + 10;
const int BLOCK = 1000;
 
struct DSU {
    int lab[mxN];
    vector<pair<int, int>> q;
    
    void reset(int n) {
        q.clear();
        for(int i = 1; i <= n; i ++) lab[i] = -1;
    }
    
    int get_root(int u) {
        return lab[u] < 0 ? u : get_root(lab[u]);
    }
    
    bool unite(int u, int v) {
        u = get_root(u);
        v = get_root(v);
        
        if(u == v) return false;
        if(lab[u] > lab[v]) swap(u, v);
        
        q.push_back({v, lab[v]});
        q.push_back({u, lab[u]});
        
        lab[u] += lab[v];
        lab[v] = u;
           
        return true;
    }
    
    void roll_back(int x) {
        while(q.size() > x) {
            int u = q.back().first;
            int vu = q.back().second;
            lab[u] = vu;
            q.pop_back();
        }
    }
    
    int get_size(int u) {
        u = get_root(u);
        return - lab[u];
    }
} F;
 
int n, m, q;
int u[mxN], v[mxN], w[mxN];
 
int t[mxN], a[mxN], b[mxN];
bool changed[mxN];
int ans[mxN];
 
int main() {
    
    cin.tie(nullptr)->sync_with_stdio(false);
    
    cin >> n >> m;
    
    for(int i = 1; i <= m; i ++) 
        cin >> u[i] >> v[i] >> w[i];
    
    cin >> q;
    
    for(int i = 1; i <= q; i ++) 
        cin >> t[i] >> a[i] >> b[i];
    
    for(int block = 0; block < BLOCK; block ++) {
        int l = block * BLOCK + 1;
        int r = min((block + 1) * BLOCK, q);
        F.reset(n);
        
        if(l > r) break ;
        
        vector<int> changes, ask;
        vector<int> edges;
        vector<vector<pair<int, int>>> adj(BLOCK + 10);
        
        for(int i = l; i <= r; i ++) {
            if(t[i] == 1) {
                changed[a[i]] = true;
                changes.push_back(a[i]);
            } else 
                ask.push_back(i);
        }
    
        for(int i = 1; i <= m; i ++) {
            if(changed[i]) continue ;
            edges.push_back(i);
        }
                
        for(int i = l; i <= r; i ++) {
            if(t[i] == 1) w[a[i]] = b[i];
            else {
                for(int x : changes) {
                    adj[i - l].push_back({x, w[x]});
                }  
            }
        }
        
        sort(ask.begin(), ask.end(), [&](const int &x, const int &y) {
            return b[x] > b[y]; 
        });
        
        sort(edges.begin(), edges.end(), [&](const int &x, const int &y) {
            return w[x] > w[y]; 
        });
        
        for(int i = 0, j = 0; i < ask.size(); i ++) {
            for(; j < edges.size() && w[edges[j]] >= b[ask[i]]; j ++) 
                F.unite(u[edges[j]], v[edges[j]]); 
            
            int curr = F.q.size();
            for(auto [x, y] : adj[ask[i] - l]) {
                if(y < b[ask[i]]) continue ;
                F.unite(u[x], v[x]);
            }
            
            ans[ask[i]] = F.get_size(a[ask[i]]);
            F.roll_back(curr);
        }
        
        for(int x : changes) changed[x] = false;
    }
    
    for(int i = 1; i <= q; i ++) if(t[i] == 2) cout << ans[i] << "\n";
    return 0;
}

Compilation message

bridges.cpp: In member function 'void DSU::roll_back(int)':
bridges.cpp:37:24: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |         while(q.size() > x) {
      |               ~~~~~~~~~^~~
bridges.cpp: In function 'int main()':
bridges.cpp:113:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |         for(int i = 0, j = 0; i < ask.size(); i ++) {
      |                               ~~^~~~~~~~~~~~
bridges.cpp:114:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |             for(; j < edges.size() && w[edges[j]] >= b[ask[i]]; j ++)
      |                   ~~^~~~~~~~~~~~~~
bridges.cpp:118:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |             for(auto [x, y] : adj[ask[i] - l]) {
      |                      ^

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 46 ms 6564 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 45 ms 6424 KB Output is correct
6 Correct 39 ms 6560 KB Output is correct
7 Correct 42 ms 6396 KB Output is correct
8 Correct 48 ms 6520 KB Output is correct
9 Correct 45 ms 6356 KB Output is correct
10 Correct 47 ms 6396 KB Output is correct
11 Correct 47 ms 6520 KB Output is correct
12 Correct 53 ms 6524 KB Output is correct
13 Correct 51 ms 6416 KB Output is correct
14 Correct 48 ms 6408 KB Output is correct
15 Correct 52 ms 6308 KB Output is correct
16 Correct 50 ms 6948 KB Output is correct
17 Correct 48 ms 6476 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 10948 KB Output is correct
2 Correct 1008 ms 10740 KB Output is correct
3 Correct 1014 ms 10936 KB Output is correct
4 Correct 1014 ms 10972 KB Output is correct
5 Correct 1018 ms 10800 KB Output is correct
6 Correct 1223 ms 10604 KB Output is correct
7 Correct 1190 ms 10632 KB Output is correct
8 Correct 1204 ms 10852 KB Output is correct
9 Correct 26 ms 4184 KB Output is correct
10 Correct 782 ms 9892 KB Output is correct
11 Correct 774 ms 9812 KB Output is correct
12 Correct 758 ms 7832 KB Output is correct
13 Correct 746 ms 7772 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 798 ms 9940 KB Output is correct
2 Correct 678 ms 8368 KB Output is correct
3 Correct 911 ms 9816 KB Output is correct
4 Correct 814 ms 9992 KB Output is correct
5 Correct 25 ms 4304 KB Output is correct
6 Correct 865 ms 9820 KB Output is correct
7 Correct 784 ms 9964 KB Output is correct
8 Correct 729 ms 9996 KB Output is correct
9 Correct 503 ms 7364 KB Output is correct
10 Correct 481 ms 7112 KB Output is correct
11 Correct 500 ms 6812 KB Output is correct
12 Correct 466 ms 6776 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1145 ms 8996 KB Output is correct
2 Correct 25 ms 4176 KB Output is correct
3 Correct 129 ms 5920 KB Output is correct
4 Correct 54 ms 6012 KB Output is correct
5 Correct 552 ms 7480 KB Output is correct
6 Correct 1111 ms 9024 KB Output is correct
7 Correct 543 ms 7480 KB Output is correct
8 Correct 524 ms 7044 KB Output is correct
9 Correct 519 ms 7156 KB Output is correct
10 Correct 523 ms 7040 KB Output is correct
11 Correct 841 ms 8100 KB Output is correct
12 Correct 819 ms 8232 KB Output is correct
13 Correct 863 ms 8224 KB Output is correct
14 Correct 494 ms 7548 KB Output is correct
15 Correct 518 ms 7464 KB Output is correct
16 Correct 1130 ms 9160 KB Output is correct
17 Correct 1150 ms 9132 KB Output is correct
18 Correct 1132 ms 9384 KB Output is correct
19 Correct 1142 ms 9664 KB Output is correct
20 Correct 967 ms 8436 KB Output is correct
21 Correct 952 ms 8496 KB Output is correct
22 Correct 1090 ms 8692 KB Output is correct
23 Correct 612 ms 6968 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 10948 KB Output is correct
2 Correct 1008 ms 10740 KB Output is correct
3 Correct 1014 ms 10936 KB Output is correct
4 Correct 1014 ms 10972 KB Output is correct
5 Correct 1018 ms 10800 KB Output is correct
6 Correct 1223 ms 10604 KB Output is correct
7 Correct 1190 ms 10632 KB Output is correct
8 Correct 1204 ms 10852 KB Output is correct
9 Correct 26 ms 4184 KB Output is correct
10 Correct 782 ms 9892 KB Output is correct
11 Correct 774 ms 9812 KB Output is correct
12 Correct 758 ms 7832 KB Output is correct
13 Correct 746 ms 7772 KB Output is correct
14 Correct 798 ms 9940 KB Output is correct
15 Correct 678 ms 8368 KB Output is correct
16 Correct 911 ms 9816 KB Output is correct
17 Correct 814 ms 9992 KB Output is correct
18 Correct 25 ms 4304 KB Output is correct
19 Correct 865 ms 9820 KB Output is correct
20 Correct 784 ms 9964 KB Output is correct
21 Correct 729 ms 9996 KB Output is correct
22 Correct 503 ms 7364 KB Output is correct
23 Correct 481 ms 7112 KB Output is correct
24 Correct 500 ms 6812 KB Output is correct
25 Correct 466 ms 6776 KB Output is correct
26 Correct 1000 ms 11048 KB Output is correct
27 Correct 1118 ms 10584 KB Output is correct
28 Correct 1052 ms 11024 KB Output is correct
29 Correct 901 ms 10888 KB Output is correct
30 Correct 1073 ms 11036 KB Output is correct
31 Correct 1081 ms 10696 KB Output is correct
32 Correct 1102 ms 10592 KB Output is correct
33 Correct 1010 ms 10948 KB Output is correct
34 Correct 1016 ms 11076 KB Output is correct
35 Correct 1044 ms 10972 KB Output is correct
36 Correct 912 ms 10800 KB Output is correct
37 Correct 909 ms 10860 KB Output is correct
38 Correct 878 ms 10728 KB Output is correct
39 Correct 635 ms 8324 KB Output is correct
40 Correct 632 ms 8392 KB Output is correct
41 Correct 636 ms 8448 KB Output is correct
42 Correct 639 ms 7768 KB Output is correct
43 Correct 644 ms 7776 KB Output is correct
44 Correct 658 ms 7756 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 46 ms 6564 KB Output is correct
4 Correct 3 ms 2648 KB Output is correct
5 Correct 45 ms 6424 KB Output is correct
6 Correct 39 ms 6560 KB Output is correct
7 Correct 42 ms 6396 KB Output is correct
8 Correct 48 ms 6520 KB Output is correct
9 Correct 45 ms 6356 KB Output is correct
10 Correct 47 ms 6396 KB Output is correct
11 Correct 47 ms 6520 KB Output is correct
12 Correct 53 ms 6524 KB Output is correct
13 Correct 51 ms 6416 KB Output is correct
14 Correct 48 ms 6408 KB Output is correct
15 Correct 52 ms 6308 KB Output is correct
16 Correct 50 ms 6948 KB Output is correct
17 Correct 48 ms 6476 KB Output is correct
18 Correct 992 ms 10948 KB Output is correct
19 Correct 1008 ms 10740 KB Output is correct
20 Correct 1014 ms 10936 KB Output is correct
21 Correct 1014 ms 10972 KB Output is correct
22 Correct 1018 ms 10800 KB Output is correct
23 Correct 1223 ms 10604 KB Output is correct
24 Correct 1190 ms 10632 KB Output is correct
25 Correct 1204 ms 10852 KB Output is correct
26 Correct 26 ms 4184 KB Output is correct
27 Correct 782 ms 9892 KB Output is correct
28 Correct 774 ms 9812 KB Output is correct
29 Correct 758 ms 7832 KB Output is correct
30 Correct 746 ms 7772 KB Output is correct
31 Correct 798 ms 9940 KB Output is correct
32 Correct 678 ms 8368 KB Output is correct
33 Correct 911 ms 9816 KB Output is correct
34 Correct 814 ms 9992 KB Output is correct
35 Correct 25 ms 4304 KB Output is correct
36 Correct 865 ms 9820 KB Output is correct
37 Correct 784 ms 9964 KB Output is correct
38 Correct 729 ms 9996 KB Output is correct
39 Correct 503 ms 7364 KB Output is correct
40 Correct 481 ms 7112 KB Output is correct
41 Correct 500 ms 6812 KB Output is correct
42 Correct 466 ms 6776 KB Output is correct
43 Correct 1145 ms 8996 KB Output is correct
44 Correct 25 ms 4176 KB Output is correct
45 Correct 129 ms 5920 KB Output is correct
46 Correct 54 ms 6012 KB Output is correct
47 Correct 552 ms 7480 KB Output is correct
48 Correct 1111 ms 9024 KB Output is correct
49 Correct 543 ms 7480 KB Output is correct
50 Correct 524 ms 7044 KB Output is correct
51 Correct 519 ms 7156 KB Output is correct
52 Correct 523 ms 7040 KB Output is correct
53 Correct 841 ms 8100 KB Output is correct
54 Correct 819 ms 8232 KB Output is correct
55 Correct 863 ms 8224 KB Output is correct
56 Correct 494 ms 7548 KB Output is correct
57 Correct 518 ms 7464 KB Output is correct
58 Correct 1130 ms 9160 KB Output is correct
59 Correct 1150 ms 9132 KB Output is correct
60 Correct 1132 ms 9384 KB Output is correct
61 Correct 1142 ms 9664 KB Output is correct
62 Correct 967 ms 8436 KB Output is correct
63 Correct 952 ms 8496 KB Output is correct
64 Correct 1090 ms 8692 KB Output is correct
65 Correct 612 ms 6968 KB Output is correct
66 Correct 1000 ms 11048 KB Output is correct
67 Correct 1118 ms 10584 KB Output is correct
68 Correct 1052 ms 11024 KB Output is correct
69 Correct 901 ms 10888 KB Output is correct
70 Correct 1073 ms 11036 KB Output is correct
71 Correct 1081 ms 10696 KB Output is correct
72 Correct 1102 ms 10592 KB Output is correct
73 Correct 1010 ms 10948 KB Output is correct
74 Correct 1016 ms 11076 KB Output is correct
75 Correct 1044 ms 10972 KB Output is correct
76 Correct 912 ms 10800 KB Output is correct
77 Correct 909 ms 10860 KB Output is correct
78 Correct 878 ms 10728 KB Output is correct
79 Correct 635 ms 8324 KB Output is correct
80 Correct 632 ms 8392 KB Output is correct
81 Correct 636 ms 8448 KB Output is correct
82 Correct 639 ms 7768 KB Output is correct
83 Correct 644 ms 7776 KB Output is correct
84 Correct 658 ms 7756 KB Output is correct
85 Correct 1573 ms 12676 KB Output is correct
86 Correct 155 ms 7808 KB Output is correct
87 Correct 91 ms 9516 KB Output is correct
88 Correct 975 ms 10952 KB Output is correct
89 Correct 1567 ms 12456 KB Output is correct
90 Correct 1022 ms 11092 KB Output is correct
91 Correct 1061 ms 10880 KB Output is correct
92 Correct 1016 ms 10844 KB Output is correct
93 Correct 1210 ms 10696 KB Output is correct
94 Correct 1326 ms 11924 KB Output is correct
95 Correct 1311 ms 12128 KB Output is correct
96 Correct 1357 ms 11588 KB Output is correct
97 Correct 674 ms 8132 KB Output is correct
98 Correct 725 ms 8196 KB Output is correct
99 Correct 1595 ms 12472 KB Output is correct
100 Correct 1578 ms 12376 KB Output is correct
101 Correct 1627 ms 12692 KB Output is correct
102 Correct 1589 ms 12992 KB Output is correct
103 Correct 1477 ms 12004 KB Output is correct
104 Correct 1462 ms 11912 KB Output is correct
105 Correct 1141 ms 8792 KB Output is correct
106 Correct 932 ms 8352 KB Output is correct
107 Correct 1092 ms 9152 KB Output is correct
108 Correct 1542 ms 12296 KB Output is correct
109 Correct 1065 ms 10872 KB Output is correct