oj.uz

Submission #672725

# Submission time Handle Problem Language Result Execution time Memory
672725 2022-12-17T18:59:38 Z jhnah917 Bridges (APIO19_bridges) C++14
100 / 100
 2222 ms 348300 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int B = 1000;

struct Edge{ int u, v, w; };
struct Query{ int op, a, b, idx; };

struct UnionFind{
    vector<int> p, s;
    stack<pair<int,int>> stk;
    UnionFind(int n) : p(n+1), s(n+1), stk() {
        iota(p.begin(), p.end(), 0);
        fill(s.begin(), s.end(), 1);
    }
    int find(int v){ return v == p[v] ? v : find(p[v]); }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v){ stk.emplace(-1, -1); return; }
        if(s[u] > s[v]) swap(u, v);
        p[u] = v; s[v] += s[u];
        stk.emplace(u, v);
    }
    void undo(){
        auto [u,v] = stk.top(); stk.pop();
        if(u != -1) p[u] = u, s[v] -= s[u];
    }
    int size(int v){ return s[find(v)]; }
};

int N, M, Q, R[101010], C[101010];
Edge E[101010];
Query Qry[101010];
vector<Edge> G[101010];

void Solve(int l, int r){
    memset(C, 0, sizeof C);
    vector<int> dy, st; // dynamic/static edge
    vector<Query> ask; // query
    for(int i=l; i<=r; i++){
        if(Qry[i].op == 1) C[Qry[i].a] = 1;
        else ask.push_back(Qry[i]);
    }
    for(int i=1; i<=M; i++) (C[i] ? dy : st).push_back(i);
    for(int i=l; i<=r; i++){
        if(Qry[i].op == 1) E[Qry[i].a].w = Qry[i].b;
        else for(auto j : dy) if(Qry[i].b <= E[j].w) G[i].push_back(E[j]);
    }

    sort(ask.begin(), ask.end(), [](auto q1, auto q2){ return q1.b > q2.b; });
    sort(st.begin(), st.end(), [](auto e1, auto e2){ return E[e1].w > E[e2].w; });

    UnionFind U(N);
    for(int i=0, j=0; i<ask.size(); i++){
        while(j < st.size() && ask[i].b <= E[st[j]].w) U.merge(E[st[j]].u, E[st[j]].v), j++;
        for(const auto &[u,v,w] : G[ask[i].idx]) U.merge(u, v);
        R[ask[i].idx] = U.size(ask[i].a);
        for(const auto &[u,v,w] : G[ask[i].idx]) U.undo();
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1; i<=M; i++) cin >> E[i].u >> E[i].v >> E[i].w;
    cin >> Q;
    for(int i=1; i<=Q; i++) cin >> Qry[i].op >> Qry[i].a >> Qry[i].b, Qry[i].idx = i;
    for(int i=1; i<=Q; i+=B) Solve(i, min(Q, i+B-1));
    for(int i=1; i<=Q; i++) if(Qry[i].op == 2) cout << R[i] << "\n";
}

Compilation message

bridges.cpp: In member function 'void UnionFind::undo()':
bridges.cpp:24:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   24 |         auto [u,v] = stk.top(); stk.pop();
      |              ^
bridges.cpp: In function 'void Solve(int, int)':
bridges.cpp:53:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i=0, j=0; i<ask.size(); i++){
      |                       ~^~~~~~~~~~~
bridges.cpp:54:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(j < st.size() && ask[i].b <= E[st[j]].w) U.merge(E[st[j]].u, E[st[j]].v), j++;
      |               ~~^~~~~~~~~~~
bridges.cpp:55:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |         for(const auto &[u,v,w] : G[ask[i].idx]) U.merge(u, v);
      |                         ^
bridges.cpp:57:25: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         for(const auto &[u,v,w] : G[ask[i].idx]) U.undo();
      |                         ^
bridges.cpp:57:25: warning: unused structured binding declaration [-Wunused-variable]
   57 |         for(const auto &[u,v,w] : G[ask[i].idx]) U.undo();
      |                         ^~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 40 ms 20296 KB Output is correct
4 Correct 5 ms 3480 KB Output is correct
5 Correct 14 ms 8096 KB Output is correct
6 Correct 12 ms 8024 KB Output is correct
7 Correct 14 ms 7960 KB Output is correct
8 Correct 15 ms 7324 KB Output is correct
9 Correct 21 ms 10824 KB Output is correct
10 Correct 16 ms 7804 KB Output is correct
11 Correct 19 ms 7700 KB Output is correct
12 Correct 20 ms 8988 KB Output is correct
13 Correct 23 ms 10592 KB Output is correct
14 Correct 21 ms 9460 KB Output is correct
15 Correct 19 ms 8040 KB Output is correct
16 Correct 17 ms 8980 KB Output is correct
17 Correct 17 ms 8976 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1357 ms 206804 KB Output is correct
2 Correct 1331 ms 209428 KB Output is correct
3 Correct 1320 ms 210424 KB Output is correct
4 Correct 1273 ms 209056 KB Output is correct
5 Correct 1288 ms 210492 KB Output is correct
6 Correct 1736 ms 348300 KB Output is correct
7 Correct 1731 ms 347476 KB Output is correct
8 Correct 1772 ms 341996 KB Output is correct
9 Correct 34 ms 6528 KB Output is correct
10 Correct 1028 ms 270508 KB Output is correct
11 Correct 981 ms 273740 KB Output is correct
12 Correct 1165 ms 146188 KB Output is correct
13 Correct 1069 ms 129648 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1118 ms 207376 KB Output is correct
2 Correct 828 ms 261636 KB Output is correct
3 Correct 1212 ms 277120 KB Output is correct
4 Correct 1087 ms 207856 KB Output is correct
5 Correct 34 ms 6604 KB Output is correct
6 Correct 1183 ms 265192 KB Output is correct
7 Correct 965 ms 189232 KB Output is correct
8 Correct 850 ms 138224 KB Output is correct
9 Correct 710 ms 109992 KB Output is correct
10 Correct 661 ms 75356 KB Output is correct
11 Correct 712 ms 103312 KB Output is correct
12 Correct 640 ms 73564 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1576 ms 7856 KB Output is correct
2 Correct 34 ms 5260 KB Output is correct
3 Correct 169 ms 5780 KB Output is correct
4 Correct 79 ms 5680 KB Output is correct
5 Correct 808 ms 7932 KB Output is correct
6 Correct 1496 ms 8008 KB Output is correct
7 Correct 836 ms 7972 KB Output is correct
8 Correct 753 ms 6632 KB Output is correct
9 Correct 750 ms 6788 KB Output is correct
10 Correct 743 ms 6832 KB Output is correct
11 Correct 1182 ms 7308 KB Output is correct
12 Correct 1160 ms 7296 KB Output is correct
13 Correct 1170 ms 7304 KB Output is correct
14 Correct 728 ms 7856 KB Output is correct
15 Correct 786 ms 8036 KB Output is correct
16 Correct 1562 ms 7808 KB Output is correct
17 Correct 1539 ms 7916 KB Output is correct
18 Correct 1521 ms 7832 KB Output is correct
19 Correct 1564 ms 7812 KB Output is correct
20 Correct 1301 ms 7548 KB Output is correct
21 Correct 1298 ms 7492 KB Output is correct
22 Correct 1504 ms 7800 KB Output is correct
23 Correct 882 ms 7336 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1357 ms 206804 KB Output is correct
2 Correct 1331 ms 209428 KB Output is correct
3 Correct 1320 ms 210424 KB Output is correct
4 Correct 1273 ms 209056 KB Output is correct
5 Correct 1288 ms 210492 KB Output is correct
6 Correct 1736 ms 348300 KB Output is correct
7 Correct 1731 ms 347476 KB Output is correct
8 Correct 1772 ms 341996 KB Output is correct
9 Correct 34 ms 6528 KB Output is correct
10 Correct 1028 ms 270508 KB Output is correct
11 Correct 981 ms 273740 KB Output is correct
12 Correct 1165 ms 146188 KB Output is correct
13 Correct 1069 ms 129648 KB Output is correct
14 Correct 1118 ms 207376 KB Output is correct
15 Correct 828 ms 261636 KB Output is correct
16 Correct 1212 ms 277120 KB Output is correct
17 Correct 1087 ms 207856 KB Output is correct
18 Correct 34 ms 6604 KB Output is correct
19 Correct 1183 ms 265192 KB Output is correct
20 Correct 965 ms 189232 KB Output is correct
21 Correct 850 ms 138224 KB Output is correct
22 Correct 710 ms 109992 KB Output is correct
23 Correct 661 ms 75356 KB Output is correct
24 Correct 712 ms 103312 KB Output is correct
25 Correct 640 ms 73564 KB Output is correct
26 Correct 1384 ms 209472 KB Output is correct
27 Correct 1642 ms 282568 KB Output is correct
28 Correct 1411 ms 203696 KB Output is correct
29 Correct 988 ms 75484 KB Output is correct
30 Correct 1555 ms 249524 KB Output is correct
31 Correct 1569 ms 255412 KB Output is correct
32 Correct 1590 ms 256480 KB Output is correct
33 Correct 1364 ms 204944 KB Output is correct
34 Correct 1369 ms 205740 KB Output is correct
35 Correct 1379 ms 206380 KB Output is correct
36 Correct 1035 ms 95556 KB Output is correct
37 Correct 1008 ms 91828 KB Output is correct
38 Correct 1026 ms 87036 KB Output is correct
39 Correct 845 ms 43952 KB Output is correct
40 Correct 844 ms 41832 KB Output is correct
41 Correct 905 ms 40200 KB Output is correct
42 Correct 860 ms 41572 KB Output is correct
43 Correct 833 ms 39980 KB Output is correct
44 Correct 818 ms 38320 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3028 KB Output is correct
2 Correct 2 ms 3028 KB Output is correct
3 Correct 40 ms 20296 KB Output is correct
4 Correct 5 ms 3480 KB Output is correct
5 Correct 14 ms 8096 KB Output is correct
6 Correct 12 ms 8024 KB Output is correct
7 Correct 14 ms 7960 KB Output is correct
8 Correct 15 ms 7324 KB Output is correct
9 Correct 21 ms 10824 KB Output is correct
10 Correct 16 ms 7804 KB Output is correct
11 Correct 19 ms 7700 KB Output is correct
12 Correct 20 ms 8988 KB Output is correct
13 Correct 23 ms 10592 KB Output is correct
14 Correct 21 ms 9460 KB Output is correct
15 Correct 19 ms 8040 KB Output is correct
16 Correct 17 ms 8980 KB Output is correct
17 Correct 17 ms 8976 KB Output is correct
18 Correct 1357 ms 206804 KB Output is correct
19 Correct 1331 ms 209428 KB Output is correct
20 Correct 1320 ms 210424 KB Output is correct
21 Correct 1273 ms 209056 KB Output is correct
22 Correct 1288 ms 210492 KB Output is correct
23 Correct 1736 ms 348300 KB Output is correct
24 Correct 1731 ms 347476 KB Output is correct
25 Correct 1772 ms 341996 KB Output is correct
26 Correct 34 ms 6528 KB Output is correct
27 Correct 1028 ms 270508 KB Output is correct
28 Correct 981 ms 273740 KB Output is correct
29 Correct 1165 ms 146188 KB Output is correct
30 Correct 1069 ms 129648 KB Output is correct
31 Correct 1118 ms 207376 KB Output is correct
32 Correct 828 ms 261636 KB Output is correct
33 Correct 1212 ms 277120 KB Output is correct
34 Correct 1087 ms 207856 KB Output is correct
35 Correct 34 ms 6604 KB Output is correct
36 Correct 1183 ms 265192 KB Output is correct
37 Correct 965 ms 189232 KB Output is correct
38 Correct 850 ms 138224 KB Output is correct
39 Correct 710 ms 109992 KB Output is correct
40 Correct 661 ms 75356 KB Output is correct
41 Correct 712 ms 103312 KB Output is correct
42 Correct 640 ms 73564 KB Output is correct
43 Correct 1576 ms 7856 KB Output is correct
44 Correct 34 ms 5260 KB Output is correct
45 Correct 169 ms 5780 KB Output is correct
46 Correct 79 ms 5680 KB Output is correct
47 Correct 808 ms 7932 KB Output is correct
48 Correct 1496 ms 8008 KB Output is correct
49 Correct 836 ms 7972 KB Output is correct
50 Correct 753 ms 6632 KB Output is correct
51 Correct 750 ms 6788 KB Output is correct
52 Correct 743 ms 6832 KB Output is correct
53 Correct 1182 ms 7308 KB Output is correct
54 Correct 1160 ms 7296 KB Output is correct
55 Correct 1170 ms 7304 KB Output is correct
56 Correct 728 ms 7856 KB Output is correct
57 Correct 786 ms 8036 KB Output is correct
58 Correct 1562 ms 7808 KB Output is correct
59 Correct 1539 ms 7916 KB Output is correct
60 Correct 1521 ms 7832 KB Output is correct
61 Correct 1564 ms 7812 KB Output is correct
62 Correct 1301 ms 7548 KB Output is correct
63 Correct 1298 ms 7492 KB Output is correct
64 Correct 1504 ms 7800 KB Output is correct
65 Correct 882 ms 7336 KB Output is correct
66 Correct 1384 ms 209472 KB Output is correct
67 Correct 1642 ms 282568 KB Output is correct
68 Correct 1411 ms 203696 KB Output is correct
69 Correct 988 ms 75484 KB Output is correct
70 Correct 1555 ms 249524 KB Output is correct
71 Correct 1569 ms 255412 KB Output is correct
72 Correct 1590 ms 256480 KB Output is correct
73 Correct 1364 ms 204944 KB Output is correct
74 Correct 1369 ms 205740 KB Output is correct
75 Correct 1379 ms 206380 KB Output is correct
76 Correct 1035 ms 95556 KB Output is correct
77 Correct 1008 ms 91828 KB Output is correct
78 Correct 1026 ms 87036 KB Output is correct
79 Correct 845 ms 43952 KB Output is correct
80 Correct 844 ms 41832 KB Output is correct
81 Correct 905 ms 40200 KB Output is correct
82 Correct 860 ms 41572 KB Output is correct
83 Correct 833 ms 39980 KB Output is correct
84 Correct 818 ms 38320 KB Output is correct
85 Correct 2143 ms 212372 KB Output is correct
86 Correct 206 ms 27584 KB Output is correct
87 Correct 132 ms 39892 KB Output is correct
88 Correct 1333 ms 244544 KB Output is correct
89 Correct 2103 ms 208480 KB Output is correct
90 Correct 1332 ms 266776 KB Output is correct
91 Correct 1395 ms 209612 KB Output is correct
92 Correct 1400 ms 209092 KB Output is correct
93 Correct 1893 ms 316712 KB Output is correct
94 Correct 1756 ms 211428 KB Output is correct
95 Correct 1731 ms 210564 KB Output is correct
96 Correct 2039 ms 323540 KB Output is correct
97 Correct 1018 ms 106932 KB Output is correct
98 Correct 1014 ms 100076 KB Output is correct
99 Correct 2118 ms 215444 KB Output is correct
100 Correct 2117 ms 211652 KB Output is correct
101 Correct 2122 ms 211916 KB Output is correct
102 Correct 2146 ms 211744 KB Output is correct
103 Correct 2222 ms 332400 KB Output is correct
104 Correct 2217 ms 332088 KB Output is correct
105 Correct 1610 ms 131640 KB Output is correct
106 Correct 1292 ms 71692 KB Output is correct
107 Correct 1540 ms 148296 KB Output is correct
108 Correct 2132 ms 316168 KB Output is correct
109 Correct 1530 ms 323064 KB Output is correct