oj.uz

Submission #751125

# Submission time Handle Problem Language Result Execution time Memory
751125 2023-05-31T05:05:31 Z Seb Bridges (APIO19_bridges) C++17
100 / 100
 2750 ms 20928 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define f first
#define s second

const ll MAXN = 1e5+5;
const ll sq = 1000;

ll sz[MAXN],p[MAXN],u[MAXN],v[MAXN],w[MAXN],t[MAXN],x[MAXN],y[MAXN],ans[MAXN];
bool changed[MAXN];
vector <ll> sk,join[sq+5];

ll padre(ll a) {
    if (sz[a]==0) {
        sz[a] = 1;
        p[a] = a;
    }
    if (p[a]==a) return a;
    return padre(p[a]);
}

void unir(ll a, ll b) {
    a = padre(a);
    b = padre(b);
    if (a==b) return;
    if (sz[a]<sz[b]) swap(a,b);
    sz[a] += sz[b];
    p[b] = a;
    sk.push_back(b);
    return;
}

void rollback(ll k) {
    while (!sk.empty() && sk.size()>k) {
        ll a = sk.back();
        sk.pop_back();
        sz[p[a]] -= sz[a];
        p[a] = a;
    }
    return;
}

void limpia() {
    for (int i=0;i<MAXN;i++) {
        p[i] = sz[i] = 0;
        changed[i] = false;
    }
    sk.clear();
    return;
}

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);
ll n,m,q;
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]>>x[i]>>y[i];
for (int l=1;l<=q;l+=sq) {
    int r = min(l+sq-1,q);
    vector <ll> ask,unchanged,upd;
    for (int i=l;i<=r;i++) {
        if (t[i]==2) ask.push_back(i);
        else {
            changed[x[i]] = true;
            upd.push_back(i);
        }
    }
    for (int i=1;i<=m;i++) if (!changed[i]) unchanged.push_back(i);
    sort(ask.begin(),ask.end(),[&](ll a, ll b) {return y[a] > y[b];});
    sort(unchanged.begin(),unchanged.end(),[&](ll a, ll b) {return w[a] > w[b];});
    for (int i=l;i<=r;i++) {
        if (t[i]==1) w[x[i]] = y[i];
        else {
            join[i-l].clear();
            for (int j=0;j<upd.size();j++) if (w[x[upd[j]]] >= y[i]) join[i-l].push_back(x[upd[j]]);
        }
    }
    int in=0;
    if (!ask.empty()) for (int i=0;i<ask.size();i++) {
        while (!unchanged.empty() && in<unchanged.size() && w[unchanged[in]] >= y[ask[i]]) {
            unir(u[unchanged[in]],v[unchanged[in]]);
            in++;
        }
        int aux;
        if (!sk.empty()) aux = sk.size();
        else aux = 0;
        for (int j=0;j<join[ask[i]-l].size();j++) unir(u[join[ask[i]-l][j]],v[join[ask[i]-l][j]]);
        ans[ask[i]] = sz[padre(x[ask[i]])];
        rollback(aux);
    }
    for (int i=l;i<=r;i++) if (t[i]==1) w[x[i]] = y[i];
    limpia();
}
for (int i=1;i<=q;i++) if (t[i]==2) cout<<ans[i]<<'\n';
return 0;
}

Compilation message

bridges.cpp: In function 'void rollback(ll)':
bridges.cpp:38:36: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   38 |     while (!sk.empty() && sk.size()>k) {
      |                           ~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for (int j=0;j<upd.size();j++) if (w[x[upd[j]]] >= y[i]) join[i-l].push_back(x[upd[j]]);
      |                          ~^~~~~~~~~~~
bridges.cpp:84:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     if (!ask.empty()) for (int i=0;i<ask.size();i++) {
      |                                    ~^~~~~~~~~~~
bridges.cpp:85:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         while (!unchanged.empty() && in<unchanged.size() && w[unchanged[in]] >= y[ask[i]]) {
      |                                      ~~^~~~~~~~~~~~~~~~~
bridges.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int j=0;j<join[ask[i]-l].size();j++) unir(u[join[ask[i]-l][j]],v[join[ask[i]-l][j]]);
      |                      ~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2004 KB Output is correct
2 Correct 1 ms 2004 KB Output is correct
3 Correct 49 ms 6632 KB Output is correct
4 Correct 5 ms 2260 KB Output is correct
5 Correct 49 ms 7036 KB Output is correct
6 Correct 39 ms 6364 KB Output is correct
7 Correct 48 ms 8128 KB Output is correct
8 Correct 49 ms 6472 KB Output is correct
9 Correct 76 ms 9804 KB Output is correct
10 Correct 47 ms 6768 KB Output is correct
11 Correct 47 ms 6476 KB Output is correct
12 Correct 59 ms 6868 KB Output is correct
13 Correct 52 ms 6780 KB Output is correct
14 Correct 48 ms 6592 KB Output is correct
15 Correct 52 ms 6560 KB Output is correct
16 Correct 61 ms 9136 KB Output is correct
17 Correct 63 ms 8132 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1354 ms 13220 KB Output is correct
2 Correct 1427 ms 13308 KB Output is correct
3 Correct 1386 ms 13236 KB Output is correct
4 Correct 1512 ms 13168 KB Output is correct
5 Correct 1549 ms 13500 KB Output is correct
6 Correct 2618 ms 16296 KB Output is correct
7 Correct 2563 ms 16132 KB Output is correct
8 Correct 2569 ms 15900 KB Output is correct
9 Correct 35 ms 5264 KB Output is correct
10 Correct 1420 ms 16152 KB Output is correct
11 Correct 1344 ms 16140 KB Output is correct
12 Correct 1347 ms 8704 KB Output is correct
13 Correct 1401 ms 15536 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1099 ms 12216 KB Output is correct
2 Correct 931 ms 14340 KB Output is correct
3 Correct 1435 ms 15320 KB Output is correct
4 Correct 1133 ms 12396 KB Output is correct
5 Correct 37 ms 5328 KB Output is correct
6 Correct 1327 ms 12272 KB Output is correct
7 Correct 1048 ms 11880 KB Output is correct
8 Correct 899 ms 11420 KB Output is correct
9 Correct 728 ms 7820 KB Output is correct
10 Correct 632 ms 7780 KB Output is correct
11 Correct 775 ms 15072 KB Output is correct
12 Correct 662 ms 15168 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 10068 KB Output is correct
2 Correct 46 ms 5276 KB Output is correct
3 Correct 156 ms 6488 KB Output is correct
4 Correct 77 ms 6464 KB Output is correct
5 Correct 859 ms 10148 KB Output is correct
6 Correct 1570 ms 10280 KB Output is correct
7 Correct 803 ms 10172 KB Output is correct
8 Correct 786 ms 7588 KB Output is correct
9 Correct 751 ms 7644 KB Output is correct
10 Correct 752 ms 8036 KB Output is correct
11 Correct 1153 ms 9128 KB Output is correct
12 Correct 1139 ms 9216 KB Output is correct
13 Correct 1177 ms 9376 KB Output is correct
14 Correct 739 ms 10232 KB Output is correct
15 Correct 814 ms 10112 KB Output is correct
16 Correct 1521 ms 10168 KB Output is correct
17 Correct 1496 ms 9988 KB Output is correct
18 Correct 1589 ms 10140 KB Output is correct
19 Correct 1603 ms 9996 KB Output is correct
20 Correct 1309 ms 9664 KB Output is correct
21 Correct 1330 ms 9672 KB Output is correct
22 Correct 1476 ms 10236 KB Output is correct
23 Correct 832 ms 9580 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1354 ms 13220 KB Output is correct
2 Correct 1427 ms 13308 KB Output is correct
3 Correct 1386 ms 13236 KB Output is correct
4 Correct 1512 ms 13168 KB Output is correct
5 Correct 1549 ms 13500 KB Output is correct
6 Correct 2618 ms 16296 KB Output is correct
7 Correct 2563 ms 16132 KB Output is correct
8 Correct 2569 ms 15900 KB Output is correct
9 Correct 35 ms 5264 KB Output is correct
10 Correct 1420 ms 16152 KB Output is correct
11 Correct 1344 ms 16140 KB Output is correct
12 Correct 1347 ms 8704 KB Output is correct
13 Correct 1401 ms 15536 KB Output is correct
14 Correct 1099 ms 12216 KB Output is correct
15 Correct 931 ms 14340 KB Output is correct
16 Correct 1435 ms 15320 KB Output is correct
17 Correct 1133 ms 12396 KB Output is correct
18 Correct 37 ms 5328 KB Output is correct
19 Correct 1327 ms 12272 KB Output is correct
20 Correct 1048 ms 11880 KB Output is correct
21 Correct 899 ms 11420 KB Output is correct
22 Correct 728 ms 7820 KB Output is correct
23 Correct 632 ms 7780 KB Output is correct
24 Correct 775 ms 15072 KB Output is correct
25 Correct 662 ms 15168 KB Output is correct
26 Correct 1423 ms 13544 KB Output is correct
27 Correct 1943 ms 16348 KB Output is correct
28 Correct 1532 ms 13132 KB Output is correct
29 Correct 1048 ms 12308 KB Output is correct
30 Correct 1855 ms 16060 KB Output is correct
31 Correct 1883 ms 16392 KB Output is correct
32 Correct 1905 ms 16232 KB Output is correct
33 Correct 1488 ms 13144 KB Output is correct
34 Correct 1512 ms 12924 KB Output is correct
35 Correct 1530 ms 13176 KB Output is correct
36 Correct 1084 ms 12536 KB Output is correct
37 Correct 1095 ms 12436 KB Output is correct
38 Correct 1079 ms 12456 KB Output is correct
39 Correct 902 ms 8832 KB Output is correct
40 Correct 891 ms 8744 KB Output is correct
41 Correct 860 ms 8916 KB Output is correct
42 Correct 850 ms 15052 KB Output is correct
43 Correct 870 ms 14956 KB Output is correct
44 Correct 881 ms 15092 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2004 KB Output is correct
2 Correct 1 ms 2004 KB Output is correct
3 Correct 49 ms 6632 KB Output is correct
4 Correct 5 ms 2260 KB Output is correct
5 Correct 49 ms 7036 KB Output is correct
6 Correct 39 ms 6364 KB Output is correct
7 Correct 48 ms 8128 KB Output is correct
8 Correct 49 ms 6472 KB Output is correct
9 Correct 76 ms 9804 KB Output is correct
10 Correct 47 ms 6768 KB Output is correct
11 Correct 47 ms 6476 KB Output is correct
12 Correct 59 ms 6868 KB Output is correct
13 Correct 52 ms 6780 KB Output is correct
14 Correct 48 ms 6592 KB Output is correct
15 Correct 52 ms 6560 KB Output is correct
16 Correct 61 ms 9136 KB Output is correct
17 Correct 63 ms 8132 KB Output is correct
18 Correct 1354 ms 13220 KB Output is correct
19 Correct 1427 ms 13308 KB Output is correct
20 Correct 1386 ms 13236 KB Output is correct
21 Correct 1512 ms 13168 KB Output is correct
22 Correct 1549 ms 13500 KB Output is correct
23 Correct 2618 ms 16296 KB Output is correct
24 Correct 2563 ms 16132 KB Output is correct
25 Correct 2569 ms 15900 KB Output is correct
26 Correct 35 ms 5264 KB Output is correct
27 Correct 1420 ms 16152 KB Output is correct
28 Correct 1344 ms 16140 KB Output is correct
29 Correct 1347 ms 8704 KB Output is correct
30 Correct 1401 ms 15536 KB Output is correct
31 Correct 1099 ms 12216 KB Output is correct
32 Correct 931 ms 14340 KB Output is correct
33 Correct 1435 ms 15320 KB Output is correct
34 Correct 1133 ms 12396 KB Output is correct
35 Correct 37 ms 5328 KB Output is correct
36 Correct 1327 ms 12272 KB Output is correct
37 Correct 1048 ms 11880 KB Output is correct
38 Correct 899 ms 11420 KB Output is correct
39 Correct 728 ms 7820 KB Output is correct
40 Correct 632 ms 7780 KB Output is correct
41 Correct 775 ms 15072 KB Output is correct
42 Correct 662 ms 15168 KB Output is correct
43 Correct 1570 ms 10068 KB Output is correct
44 Correct 46 ms 5276 KB Output is correct
45 Correct 156 ms 6488 KB Output is correct
46 Correct 77 ms 6464 KB Output is correct
47 Correct 859 ms 10148 KB Output is correct
48 Correct 1570 ms 10280 KB Output is correct
49 Correct 803 ms 10172 KB Output is correct
50 Correct 786 ms 7588 KB Output is correct
51 Correct 751 ms 7644 KB Output is correct
52 Correct 752 ms 8036 KB Output is correct
53 Correct 1153 ms 9128 KB Output is correct
54 Correct 1139 ms 9216 KB Output is correct
55 Correct 1177 ms 9376 KB Output is correct
56 Correct 739 ms 10232 KB Output is correct
57 Correct 814 ms 10112 KB Output is correct
58 Correct 1521 ms 10168 KB Output is correct
59 Correct 1496 ms 9988 KB Output is correct
60 Correct 1589 ms 10140 KB Output is correct
61 Correct 1603 ms 9996 KB Output is correct
62 Correct 1309 ms 9664 KB Output is correct
63 Correct 1330 ms 9672 KB Output is correct
64 Correct 1476 ms 10236 KB Output is correct
65 Correct 832 ms 9580 KB Output is correct
66 Correct 1423 ms 13544 KB Output is correct
67 Correct 1943 ms 16348 KB Output is correct
68 Correct 1532 ms 13132 KB Output is correct
69 Correct 1048 ms 12308 KB Output is correct
70 Correct 1855 ms 16060 KB Output is correct
71 Correct 1883 ms 16392 KB Output is correct
72 Correct 1905 ms 16232 KB Output is correct
73 Correct 1488 ms 13144 KB Output is correct
74 Correct 1512 ms 12924 KB Output is correct
75 Correct 1530 ms 13176 KB Output is correct
76 Correct 1084 ms 12536 KB Output is correct
77 Correct 1095 ms 12436 KB Output is correct
78 Correct 1079 ms 12456 KB Output is correct
79 Correct 902 ms 8832 KB Output is correct
80 Correct 891 ms 8744 KB Output is correct
81 Correct 860 ms 8916 KB Output is correct
82 Correct 850 ms 15052 KB Output is correct
83 Correct 870 ms 14956 KB Output is correct
84 Correct 881 ms 15092 KB Output is correct
85 Correct 2262 ms 15236 KB Output is correct
86 Correct 205 ms 10576 KB Output is correct
87 Correct 156 ms 13088 KB Output is correct
88 Correct 1582 ms 18108 KB Output is correct
89 Correct 2201 ms 15300 KB Output is correct
90 Correct 1599 ms 18312 KB Output is correct
91 Correct 1549 ms 13148 KB Output is correct
92 Correct 1512 ms 12800 KB Output is correct
93 Correct 2407 ms 15636 KB Output is correct
94 Correct 1878 ms 14508 KB Output is correct
95 Correct 1840 ms 14444 KB Output is correct
96 Correct 2596 ms 17268 KB Output is correct
97 Correct 1102 ms 10812 KB Output is correct
98 Correct 1232 ms 18224 KB Output is correct
99 Correct 2236 ms 15432 KB Output is correct
100 Correct 2233 ms 14780 KB Output is correct
101 Correct 2311 ms 15096 KB Output is correct
102 Correct 2284 ms 15188 KB Output is correct
103 Correct 2729 ms 17600 KB Output is correct
104 Correct 2750 ms 20928 KB Output is correct
105 Correct 1854 ms 20724 KB Output is correct
106 Correct 1414 ms 20312 KB Output is correct
107 Correct 1717 ms 14000 KB Output is correct
108 Correct 2529 ms 19588 KB Output is correct
109 Correct 2156 ms 19700 KB Output is correct