oj.uz

Submission #448719

# Submission time Handle Problem Language Result Execution time Memory
448719 2021-08-01T01:06:04 Z JovanB Bridges (APIO19_bridges) C++17
100 / 100
 2315 ms 111816 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 50000;
const int M = 100000;
const int K = 600;

int ea[M+5];
int eb[M+5];
int ec[M+5];
bool changed[M+5];

int qt[M+5];
int qa[M+5];
int qb[M+5];

struct DSU{
    int n;
    int par[N+5];
    int sz[N+5];
    void init(int _n){
        n = _n;
        for(int i=1; i<=n; i++){
            par[i] = i;
            sz[i] = 1;
        }
    }
    int root(int x){ return (x == par[x] ? x : par[x] = root(par[x])); }
    void povezi(int a, int b){
        a = root(a);
        b = root(b);
        if(a == b) return;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
    }
} dsu;

int sol[M+5];

const int INF = 1000000007;

vector <int> ima[M+5];
int gde[M+5];

vector <pair <int, int>> unerased;

vector <int> graf[N+5];

bool visited[N+5];

int dfs(int v){
    int svi = dsu.sz[v];
    visited[v] = 1;
    for(auto c : graf[v]) if(!visited[c]) svi += dfs(c);
    return svi;
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n, m;
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> ea[i] >> eb[i] >> ec[i];
        unerased.push_back({ec[i], i});
    }
    int qrs;
    cin >> qrs;
    int qq = 0;
    sort(unerased.begin(), unerased.end());
    for(int ql=1; ql<=qrs; ql+=K){
        int qr = min(qrs, ql+K-1);
        dsu.init(n);
        vector <pair <int, pair <int, int>>> dvec;
        vector <int> ch;
        for(int i=ql; i<=qr; i++){
            cin >> qt[i] >> qa[i] >> qb[i];
            if(qt[i] == 1){
                if(!changed[qa[i]]){
                    ch.push_back(qa[i]);
                }
                changed[qa[i]] = 1;
            }
            else{
                qq++;
                gde[i] = qq;
                dvec.push_back({qb[i], {qq, qa[i]}});
            }
        }
        sort(dvec.begin(), dvec.end());
        vector <pair <int, pair <int, int>>> vec;
        int j = 0;
        for(auto c : unerased){
            while(j < dvec.size() && c.first >= dvec[j].first){
                vec.push_back(dvec[j]);
                j++;
            }
            if(!changed[c.second]) vec.push_back({c.first, {INF, c.second}});
        }
        while(j < dvec.size()){
            vec.push_back(dvec[j]);
            j++;
        }
        reverse(vec.begin(), vec.end());
        for(int i=ql; i<=qr; i++){
            if(qt[i] == 1) ec[qa[i]] = qb[i];
            else{
                for(auto c : ch){
                    if(ec[c] >= qb[i]) ima[gde[i]].push_back(c);
                }
            }
        }
        for(auto x : vec){
            if(x.second.first == INF) dsu.povezi(ea[x.second.second], eb[x.second.second]);
            else{
                int ind = x.second.first;
                int p = x.second.second;
                p = dsu.root(p);
                for(auto c : ima[ind]){
                    int a = dsu.root(ea[c]);
                    int b = dsu.root(eb[c]);
                    if(a == b) continue;
                    graf[a].push_back(b);
                    graf[b].push_back(a);
                }
                sol[ind] = dfs(p);
                visited[p] = 0;
                for(auto c : ima[ind]){
                    int a = dsu.root(ea[c]);
                    int b = dsu.root(eb[c]);
                    graf[a].clear();
                    graf[b].clear();
                    visited[a] = visited[b] = 0;
                }
            }
        }
        for(int i=ql; i<=qr; i++) if(gde[i]) ima[gde[i]].clear();
        vector <pair <int, int>> nv;
        vector <pair <int, int>> dv;
        for(auto c : ch){
            dv.push_back({ec[c], c});
        }
        sort(dv.begin(), dv.end());
        j = 0;
        for(auto c : unerased){
            while(j < dv.size() && c.first >= dv[j].first){
                nv.push_back(dv[j]);
                j++;
            }
            if(!changed[c.second]) nv.push_back(c);
        }
        while(j < dv.size()){
            nv.push_back(dv[j]);
            j++;
        }
        unerased = nv;
        nv.clear();
        nv.shrink_to_fit();
        for(auto c : ch) changed[c] = 0;
    }
    for(int i=1; i<=qq; i++) cout << sol[i] << "\n";
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:100:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             while(j < dvec.size() && c.first >= dvec[j].first){
      |                   ~~^~~~~~~~~~~~~
bridges.cpp:106:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         while(j < dvec.size()){
      |               ~~^~~~~~~~~~~~~
bridges.cpp:152:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |             while(j < dv.size() && c.first >= dv[j].first){
      |                   ~~^~~~~~~~~~~
bridges.cpp:158:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  158 |         while(j < dv.size()){
      |               ~~^~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3856 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 36 ms 7500 KB Output is correct
4 Correct 7 ms 4172 KB Output is correct
5 Correct 22 ms 5708 KB Output is correct
6 Correct 20 ms 5700 KB Output is correct
7 Correct 23 ms 5712 KB Output is correct
8 Correct 21 ms 5492 KB Output is correct
9 Correct 29 ms 6712 KB Output is correct
10 Correct 22 ms 5660 KB Output is correct
11 Correct 22 ms 5516 KB Output is correct
12 Correct 24 ms 6000 KB Output is correct
13 Correct 28 ms 6024 KB Output is correct
14 Correct 26 ms 5848 KB Output is correct
15 Correct 25 ms 5672 KB Output is correct
16 Correct 24 ms 6004 KB Output is correct
17 Correct 24 ms 5952 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 53892 KB Output is correct
2 Correct 1589 ms 53708 KB Output is correct
3 Correct 1490 ms 53732 KB Output is correct
4 Correct 1501 ms 53428 KB Output is correct
5 Correct 1499 ms 53752 KB Output is correct
6 Correct 2270 ms 109588 KB Output is correct
7 Correct 2140 ms 110004 KB Output is correct
8 Correct 2114 ms 109880 KB Output is correct
9 Correct 46 ms 6084 KB Output is correct
10 Correct 1758 ms 85444 KB Output is correct
11 Correct 1589 ms 69152 KB Output is correct
12 Correct 1215 ms 39428 KB Output is correct
13 Correct 1208 ms 49044 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1187 ms 52136 KB Output is correct
2 Correct 1039 ms 78356 KB Output is correct
3 Correct 1444 ms 80992 KB Output is correct
4 Correct 1159 ms 51740 KB Output is correct
5 Correct 60 ms 6020 KB Output is correct
6 Correct 1358 ms 65112 KB Output is correct
7 Correct 1056 ms 46320 KB Output is correct
8 Correct 867 ms 36060 KB Output is correct
9 Correct 735 ms 28536 KB Output is correct
10 Correct 669 ms 22232 KB Output is correct
11 Correct 793 ms 27144 KB Output is correct
12 Correct 687 ms 21244 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1358 ms 11756 KB Output is correct
2 Correct 46 ms 5952 KB Output is correct
3 Correct 141 ms 9540 KB Output is correct
4 Correct 123 ms 9712 KB Output is correct
5 Correct 1154 ms 11732 KB Output is correct
6 Correct 1397 ms 11720 KB Output is correct
7 Correct 1133 ms 11732 KB Output is correct
8 Correct 751 ms 9036 KB Output is correct
9 Correct 767 ms 9068 KB Output is correct
10 Correct 764 ms 9052 KB Output is correct
11 Correct 1211 ms 10844 KB Output is correct
12 Correct 1212 ms 10872 KB Output is correct
13 Correct 1238 ms 10808 KB Output is correct
14 Correct 1111 ms 11792 KB Output is correct
15 Correct 1056 ms 11724 KB Output is correct
16 Correct 1435 ms 11692 KB Output is correct
17 Correct 1441 ms 11648 KB Output is correct
18 Correct 1470 ms 11700 KB Output is correct
19 Correct 1475 ms 11824 KB Output is correct
20 Correct 1375 ms 11088 KB Output is correct
21 Correct 1366 ms 11080 KB Output is correct
22 Correct 1461 ms 11540 KB Output is correct
23 Correct 1178 ms 11024 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1461 ms 53892 KB Output is correct
2 Correct 1589 ms 53708 KB Output is correct
3 Correct 1490 ms 53732 KB Output is correct
4 Correct 1501 ms 53428 KB Output is correct
5 Correct 1499 ms 53752 KB Output is correct
6 Correct 2270 ms 109588 KB Output is correct
7 Correct 2140 ms 110004 KB Output is correct
8 Correct 2114 ms 109880 KB Output is correct
9 Correct 46 ms 6084 KB Output is correct
10 Correct 1758 ms 85444 KB Output is correct
11 Correct 1589 ms 69152 KB Output is correct
12 Correct 1215 ms 39428 KB Output is correct
13 Correct 1208 ms 49044 KB Output is correct
14 Correct 1187 ms 52136 KB Output is correct
15 Correct 1039 ms 78356 KB Output is correct
16 Correct 1444 ms 80992 KB Output is correct
17 Correct 1159 ms 51740 KB Output is correct
18 Correct 60 ms 6020 KB Output is correct
19 Correct 1358 ms 65112 KB Output is correct
20 Correct 1056 ms 46320 KB Output is correct
21 Correct 867 ms 36060 KB Output is correct
22 Correct 735 ms 28536 KB Output is correct
23 Correct 669 ms 22232 KB Output is correct
24 Correct 793 ms 27144 KB Output is correct
25 Correct 687 ms 21244 KB Output is correct
26 Correct 1495 ms 53272 KB Output is correct
27 Correct 1896 ms 82464 KB Output is correct
28 Correct 1651 ms 52504 KB Output is correct
29 Correct 1087 ms 24632 KB Output is correct
30 Correct 1893 ms 68508 KB Output is correct
31 Correct 1921 ms 71088 KB Output is correct
32 Correct 1899 ms 71816 KB Output is correct
33 Correct 1611 ms 51832 KB Output is correct
34 Correct 1613 ms 52252 KB Output is correct
35 Correct 1654 ms 52268 KB Output is correct
36 Correct 1184 ms 28904 KB Output is correct
37 Correct 1266 ms 28068 KB Output is correct
38 Correct 1162 ms 27048 KB Output is correct
39 Correct 949 ms 17148 KB Output is correct
40 Correct 919 ms 16768 KB Output is correct
41 Correct 911 ms 16360 KB Output is correct
42 Correct 924 ms 16540 KB Output is correct
43 Correct 948 ms 16196 KB Output is correct
44 Correct 943 ms 15880 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3856 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 36 ms 7500 KB Output is correct
4 Correct 7 ms 4172 KB Output is correct
5 Correct 22 ms 5708 KB Output is correct
6 Correct 20 ms 5700 KB Output is correct
7 Correct 23 ms 5712 KB Output is correct
8 Correct 21 ms 5492 KB Output is correct
9 Correct 29 ms 6712 KB Output is correct
10 Correct 22 ms 5660 KB Output is correct
11 Correct 22 ms 5516 KB Output is correct
12 Correct 24 ms 6000 KB Output is correct
13 Correct 28 ms 6024 KB Output is correct
14 Correct 26 ms 5848 KB Output is correct
15 Correct 25 ms 5672 KB Output is correct
16 Correct 24 ms 6004 KB Output is correct
17 Correct 24 ms 5952 KB Output is correct
18 Correct 1461 ms 53892 KB Output is correct
19 Correct 1589 ms 53708 KB Output is correct
20 Correct 1490 ms 53732 KB Output is correct
21 Correct 1501 ms 53428 KB Output is correct
22 Correct 1499 ms 53752 KB Output is correct
23 Correct 2270 ms 109588 KB Output is correct
24 Correct 2140 ms 110004 KB Output is correct
25 Correct 2114 ms 109880 KB Output is correct
26 Correct 46 ms 6084 KB Output is correct
27 Correct 1758 ms 85444 KB Output is correct
28 Correct 1589 ms 69152 KB Output is correct
29 Correct 1215 ms 39428 KB Output is correct
30 Correct 1208 ms 49044 KB Output is correct
31 Correct 1187 ms 52136 KB Output is correct
32 Correct 1039 ms 78356 KB Output is correct
33 Correct 1444 ms 80992 KB Output is correct
34 Correct 1159 ms 51740 KB Output is correct
35 Correct 60 ms 6020 KB Output is correct
36 Correct 1358 ms 65112 KB Output is correct
37 Correct 1056 ms 46320 KB Output is correct
38 Correct 867 ms 36060 KB Output is correct
39 Correct 735 ms 28536 KB Output is correct
40 Correct 669 ms 22232 KB Output is correct
41 Correct 793 ms 27144 KB Output is correct
42 Correct 687 ms 21244 KB Output is correct
43 Correct 1358 ms 11756 KB Output is correct
44 Correct 46 ms 5952 KB Output is correct
45 Correct 141 ms 9540 KB Output is correct
46 Correct 123 ms 9712 KB Output is correct
47 Correct 1154 ms 11732 KB Output is correct
48 Correct 1397 ms 11720 KB Output is correct
49 Correct 1133 ms 11732 KB Output is correct
50 Correct 751 ms 9036 KB Output is correct
51 Correct 767 ms 9068 KB Output is correct
52 Correct 764 ms 9052 KB Output is correct
53 Correct 1211 ms 10844 KB Output is correct
54 Correct 1212 ms 10872 KB Output is correct
55 Correct 1238 ms 10808 KB Output is correct
56 Correct 1111 ms 11792 KB Output is correct
57 Correct 1056 ms 11724 KB Output is correct
58 Correct 1435 ms 11692 KB Output is correct
59 Correct 1441 ms 11648 KB Output is correct
60 Correct 1470 ms 11700 KB Output is correct
61 Correct 1475 ms 11824 KB Output is correct
62 Correct 1375 ms 11088 KB Output is correct
63 Correct 1366 ms 11080 KB Output is correct
64 Correct 1461 ms 11540 KB Output is correct
65 Correct 1178 ms 11024 KB Output is correct
66 Correct 1495 ms 53272 KB Output is correct
67 Correct 1896 ms 82464 KB Output is correct
68 Correct 1651 ms 52504 KB Output is correct
69 Correct 1087 ms 24632 KB Output is correct
70 Correct 1893 ms 68508 KB Output is correct
71 Correct 1921 ms 71088 KB Output is correct
72 Correct 1899 ms 71816 KB Output is correct
73 Correct 1611 ms 51832 KB Output is correct
74 Correct 1613 ms 52252 KB Output is correct
75 Correct 1654 ms 52268 KB Output is correct
76 Correct 1184 ms 28904 KB Output is correct
77 Correct 1266 ms 28068 KB Output is correct
78 Correct 1162 ms 27048 KB Output is correct
79 Correct 949 ms 17148 KB Output is correct
80 Correct 919 ms 16768 KB Output is correct
81 Correct 911 ms 16360 KB Output is correct
82 Correct 924 ms 16540 KB Output is correct
83 Correct 948 ms 16196 KB Output is correct
84 Correct 943 ms 15880 KB Output is correct
85 Correct 2108 ms 56200 KB Output is correct
86 Correct 201 ms 13800 KB Output is correct
87 Correct 208 ms 19312 KB Output is correct
88 Correct 1868 ms 68540 KB Output is correct
89 Correct 2075 ms 55280 KB Output is correct
90 Correct 1855 ms 68992 KB Output is correct
91 Correct 1697 ms 53536 KB Output is correct
92 Correct 1685 ms 53312 KB Output is correct
93 Correct 2315 ms 109720 KB Output is correct
94 Correct 1880 ms 55096 KB Output is correct
95 Correct 1902 ms 55432 KB Output is correct
96 Correct 2174 ms 110428 KB Output is correct
97 Correct 1345 ms 32168 KB Output is correct
98 Correct 1459 ms 34716 KB Output is correct
99 Correct 2101 ms 57012 KB Output is correct
100 Correct 2037 ms 56172 KB Output is correct
101 Correct 2133 ms 56032 KB Output is correct
102 Correct 2155 ms 55784 KB Output is correct
103 Correct 2216 ms 111816 KB Output is correct
104 Correct 2202 ms 111704 KB Output is correct
105 Correct 1617 ms 50536 KB Output is correct
106 Correct 1383 ms 30992 KB Output is correct
107 Correct 1616 ms 39612 KB Output is correct
108 Correct 2191 ms 82732 KB Output is correct
109 Correct 2035 ms 108520 KB Output is correct