oj.uz

Submission #648869

# Submission time Handle Problem Language Result Execution time Memory
648869 2022-10-08T15:21:25 Z PoonYaPat Bridges (APIO19_bridges) C++14
100 / 100
 2124 ms 150840 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int sq=1000,MX=100001;
int n,m,q,p[MX],sz[MX],a[MX],b[MX],w[MX],mode[MX],x[MX],y[MX],ans[MX];
stack<int> st;
vector<int> join[MX];

int find(int x) {
    while (x!=p[x]) x=p[x];
    return x;
}

void unite(int x, int y) {
    x=find(x); y=find(y);
    if (x==y) return;
    if (sz[x]<sz[y]) swap(x,y);
    p[y]=x;
    sz[x]+=sz[y];
    st.push(y);
}

void backward(int x) {
    while (st.size()>x) {
        int node=st.top();
        st.pop();
        sz[p[node]]-=sz[node];
        p[node]=node;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for (int i=1; i<=m; ++i) cin>>a[i]>>b[i]>>w[i];
    cin>>q;
    for (int i=0; i<q; ++i) cin>>mode[i]>>x[i]>>y[i];

    for (int k=0; k<q; k+=sq) {
        int l=k, r=min(q-1,k+sq-1);

        vector<int> ask,unchange,change;
        bool dif[100001];
        memset(dif,0,sizeof(dif));
        for (int i=1; i<=n; ++i) sz[i]=1,p[i]=i;

        for (int i=l; i<=r; ++i) {
            if (mode[i]==1) { //change
                dif[x[i]]=true;
                change.push_back(i); //collect round
            } else ask.push_back(i);
        }

        for (int i=1; i<=m; ++i) {
            if (!dif[i]) unchange.push_back(i); //collect edge
        }

        for (int i=l; i<=r; ++i) {
            if (mode[i]==2) {
                for (auto s : change) {
                    if (w[x[s]]>=y[i]) join[i].push_back(x[s]);
                }
            } else w[x[i]]=y[i];
        }

        sort(ask.begin(),ask.end(), [&](int a, int b){return y[a]>y[b];});
        sort(unchange.begin(),unchange.end(), [&](int a, int b){return w[a]>w[b];});

        int idx=0;
        for (auto i : ask) {
            //weight of the car is y[i] from city x[i]
            while (idx<unchange.size() && w[unchange[idx]]>=y[i]) unite(a[unchange[idx]],b[unchange[idx]]), ++idx;

            int pre=st.size();
            for (auto s : join[i]) unite(a[s],b[s]);
            ans[i]=sz[find(x[i])];
            backward(pre);
        }
    }

    for (int i=0; i<q; ++i) if (mode[i]==2) cout<<ans[i]<<"\n";
}

Compilation message

bridges.cpp: In function 'void backward(int)':
bridges.cpp:25:21: warning: comparison of integer expressions of different signedness: 'std::stack<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     while (st.size()>x) {
      |            ~~~~~~~~~^~
bridges.cpp: In function 'int main()':
bridges.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |             while (idx<unchange.size() && w[unchange[idx]]>=y[i]) unite(a[unchange[idx]],b[unchange[idx]]), ++idx;
      |                    ~~~^~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 40 ms 9544 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 40 ms 10388 KB Output is correct
6 Correct 31 ms 10580 KB Output is correct
7 Correct 37 ms 10572 KB Output is correct
8 Correct 42 ms 8936 KB Output is correct
9 Correct 54 ms 14924 KB Output is correct
10 Correct 41 ms 9812 KB Output is correct
11 Correct 44 ms 9588 KB Output is correct
12 Correct 51 ms 12124 KB Output is correct
13 Correct 50 ms 10120 KB Output is correct
14 Correct 46 ms 9320 KB Output is correct
15 Correct 49 ms 10300 KB Output is correct
16 Correct 44 ms 13104 KB Output is correct
17 Correct 43 ms 12228 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1415 ms 92876 KB Output is correct
2 Correct 1410 ms 92772 KB Output is correct
3 Correct 1381 ms 93072 KB Output is correct
4 Correct 1470 ms 92580 KB Output is correct
5 Correct 1457 ms 93228 KB Output is correct
6 Correct 2059 ms 150840 KB Output is correct
7 Correct 2124 ms 147448 KB Output is correct
8 Correct 2108 ms 147204 KB Output is correct
9 Correct 35 ms 4428 KB Output is correct
10 Correct 1251 ms 118628 KB Output is correct
11 Correct 1155 ms 117700 KB Output is correct
12 Correct 1223 ms 73104 KB Output is correct
13 Correct 1199 ms 65808 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1109 ms 85752 KB Output is correct
2 Correct 903 ms 100928 KB Output is correct
3 Correct 1342 ms 113852 KB Output is correct
4 Correct 1123 ms 85296 KB Output is correct
5 Correct 33 ms 4456 KB Output is correct
6 Correct 1317 ms 105148 KB Output is correct
7 Correct 1008 ms 77392 KB Output is correct
8 Correct 868 ms 61420 KB Output is correct
9 Correct 733 ms 53536 KB Output is correct
10 Correct 681 ms 41924 KB Output is correct
11 Correct 788 ms 50824 KB Output is correct
12 Correct 689 ms 40244 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1545 ms 27148 KB Output is correct
2 Correct 36 ms 5872 KB Output is correct
3 Correct 157 ms 7028 KB Output is correct
4 Correct 101 ms 7012 KB Output is correct
5 Correct 734 ms 29612 KB Output is correct
6 Correct 1475 ms 31076 KB Output is correct
7 Correct 761 ms 29560 KB Output is correct
8 Correct 760 ms 29172 KB Output is correct
9 Correct 745 ms 29024 KB Output is correct
10 Correct 749 ms 29004 KB Output is correct
11 Correct 1107 ms 30288 KB Output is correct
12 Correct 1103 ms 30412 KB Output is correct
13 Correct 1164 ms 30416 KB Output is correct
14 Correct 673 ms 29476 KB Output is correct
15 Correct 718 ms 29636 KB Output is correct
16 Correct 1500 ms 31176 KB Output is correct
17 Correct 1485 ms 31348 KB Output is correct
18 Correct 1500 ms 31480 KB Output is correct
19 Correct 1543 ms 31464 KB Output is correct
20 Correct 1276 ms 30756 KB Output is correct
21 Correct 1266 ms 30684 KB Output is correct
22 Correct 1443 ms 30668 KB Output is correct
23 Correct 844 ms 27332 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1415 ms 92876 KB Output is correct
2 Correct 1410 ms 92772 KB Output is correct
3 Correct 1381 ms 93072 KB Output is correct
4 Correct 1470 ms 92580 KB Output is correct
5 Correct 1457 ms 93228 KB Output is correct
6 Correct 2059 ms 150840 KB Output is correct
7 Correct 2124 ms 147448 KB Output is correct
8 Correct 2108 ms 147204 KB Output is correct
9 Correct 35 ms 4428 KB Output is correct
10 Correct 1251 ms 118628 KB Output is correct
11 Correct 1155 ms 117700 KB Output is correct
12 Correct 1223 ms 73104 KB Output is correct
13 Correct 1199 ms 65808 KB Output is correct
14 Correct 1109 ms 85752 KB Output is correct
15 Correct 903 ms 100928 KB Output is correct
16 Correct 1342 ms 113852 KB Output is correct
17 Correct 1123 ms 85296 KB Output is correct
18 Correct 33 ms 4456 KB Output is correct
19 Correct 1317 ms 105148 KB Output is correct
20 Correct 1008 ms 77392 KB Output is correct
21 Correct 868 ms 61420 KB Output is correct
22 Correct 733 ms 53536 KB Output is correct
23 Correct 681 ms 41924 KB Output is correct
24 Correct 788 ms 50824 KB Output is correct
25 Correct 689 ms 40244 KB Output is correct
26 Correct 1397 ms 92864 KB Output is correct
27 Correct 1743 ms 122220 KB Output is correct
28 Correct 1445 ms 91048 KB Output is correct
29 Correct 1020 ms 48096 KB Output is correct
30 Correct 1662 ms 108532 KB Output is correct
31 Correct 1695 ms 111028 KB Output is correct
32 Correct 1706 ms 111744 KB Output is correct
33 Correct 1443 ms 91472 KB Output is correct
34 Correct 1446 ms 91584 KB Output is correct
35 Correct 1422 ms 91856 KB Output is correct
36 Correct 1080 ms 55140 KB Output is correct
37 Correct 1050 ms 53772 KB Output is correct
38 Correct 1050 ms 52312 KB Output is correct
39 Correct 893 ms 38420 KB Output is correct
40 Correct 867 ms 37704 KB Output is correct
41 Correct 854 ms 37100 KB Output is correct
42 Correct 822 ms 35908 KB Output is correct
43 Correct 818 ms 35332 KB Output is correct
44 Correct 796 ms 34732 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 40 ms 9544 KB Output is correct
4 Correct 5 ms 2900 KB Output is correct
5 Correct 40 ms 10388 KB Output is correct
6 Correct 31 ms 10580 KB Output is correct
7 Correct 37 ms 10572 KB Output is correct
8 Correct 42 ms 8936 KB Output is correct
9 Correct 54 ms 14924 KB Output is correct
10 Correct 41 ms 9812 KB Output is correct
11 Correct 44 ms 9588 KB Output is correct
12 Correct 51 ms 12124 KB Output is correct
13 Correct 50 ms 10120 KB Output is correct
14 Correct 46 ms 9320 KB Output is correct
15 Correct 49 ms 10300 KB Output is correct
16 Correct 44 ms 13104 KB Output is correct
17 Correct 43 ms 12228 KB Output is correct
18 Correct 1415 ms 92876 KB Output is correct
19 Correct 1410 ms 92772 KB Output is correct
20 Correct 1381 ms 93072 KB Output is correct
21 Correct 1470 ms 92580 KB Output is correct
22 Correct 1457 ms 93228 KB Output is correct
23 Correct 2059 ms 150840 KB Output is correct
24 Correct 2124 ms 147448 KB Output is correct
25 Correct 2108 ms 147204 KB Output is correct
26 Correct 35 ms 4428 KB Output is correct
27 Correct 1251 ms 118628 KB Output is correct
28 Correct 1155 ms 117700 KB Output is correct
29 Correct 1223 ms 73104 KB Output is correct
30 Correct 1199 ms 65808 KB Output is correct
31 Correct 1109 ms 85752 KB Output is correct
32 Correct 903 ms 100928 KB Output is correct
33 Correct 1342 ms 113852 KB Output is correct
34 Correct 1123 ms 85296 KB Output is correct
35 Correct 33 ms 4456 KB Output is correct
36 Correct 1317 ms 105148 KB Output is correct
37 Correct 1008 ms 77392 KB Output is correct
38 Correct 868 ms 61420 KB Output is correct
39 Correct 733 ms 53536 KB Output is correct
40 Correct 681 ms 41924 KB Output is correct
41 Correct 788 ms 50824 KB Output is correct
42 Correct 689 ms 40244 KB Output is correct
43 Correct 1545 ms 27148 KB Output is correct
44 Correct 36 ms 5872 KB Output is correct
45 Correct 157 ms 7028 KB Output is correct
46 Correct 101 ms 7012 KB Output is correct
47 Correct 734 ms 29612 KB Output is correct
48 Correct 1475 ms 31076 KB Output is correct
49 Correct 761 ms 29560 KB Output is correct
50 Correct 760 ms 29172 KB Output is correct
51 Correct 745 ms 29024 KB Output is correct
52 Correct 749 ms 29004 KB Output is correct
53 Correct 1107 ms 30288 KB Output is correct
54 Correct 1103 ms 30412 KB Output is correct
55 Correct 1164 ms 30416 KB Output is correct
56 Correct 673 ms 29476 KB Output is correct
57 Correct 718 ms 29636 KB Output is correct
58 Correct 1500 ms 31176 KB Output is correct
59 Correct 1485 ms 31348 KB Output is correct
60 Correct 1500 ms 31480 KB Output is correct
61 Correct 1543 ms 31464 KB Output is correct
62 Correct 1276 ms 30756 KB Output is correct
63 Correct 1266 ms 30684 KB Output is correct
64 Correct 1443 ms 30668 KB Output is correct
65 Correct 844 ms 27332 KB Output is correct
66 Correct 1397 ms 92864 KB Output is correct
67 Correct 1743 ms 122220 KB Output is correct
68 Correct 1445 ms 91048 KB Output is correct
69 Correct 1020 ms 48096 KB Output is correct
70 Correct 1662 ms 108532 KB Output is correct
71 Correct 1695 ms 111028 KB Output is correct
72 Correct 1706 ms 111744 KB Output is correct
73 Correct 1443 ms 91472 KB Output is correct
74 Correct 1446 ms 91584 KB Output is correct
75 Correct 1422 ms 91856 KB Output is correct
76 Correct 1080 ms 55140 KB Output is correct
77 Correct 1050 ms 53772 KB Output is correct
78 Correct 1050 ms 52312 KB Output is correct
79 Correct 893 ms 38420 KB Output is correct
80 Correct 867 ms 37704 KB Output is correct
81 Correct 854 ms 37100 KB Output is correct
82 Correct 822 ms 35908 KB Output is correct
83 Correct 818 ms 35332 KB Output is correct
84 Correct 796 ms 34732 KB Output is correct
85 Correct 1930 ms 97660 KB Output is correct
86 Correct 190 ms 13020 KB Output is correct
87 Correct 123 ms 17548 KB Output is correct
88 Correct 1211 ms 109596 KB Output is correct
89 Correct 1955 ms 96132 KB Output is correct
90 Correct 1209 ms 118100 KB Output is correct
91 Correct 1459 ms 95600 KB Output is correct
92 Correct 1433 ms 95420 KB Output is correct
93 Correct 2097 ms 133232 KB Output is correct
94 Correct 1637 ms 96900 KB Output is correct
95 Correct 1632 ms 96920 KB Output is correct
96 Correct 1890 ms 137596 KB Output is correct
97 Correct 885 ms 62380 KB Output is correct
98 Correct 916 ms 58932 KB Output is correct
99 Correct 1985 ms 98692 KB Output is correct
100 Correct 1919 ms 97432 KB Output is correct
101 Correct 2011 ms 97700 KB Output is correct
102 Correct 1957 ms 97780 KB Output is correct
103 Correct 2102 ms 142864 KB Output is correct
104 Correct 2116 ms 142400 KB Output is correct
105 Correct 1524 ms 70264 KB Output is correct
106 Correct 1255 ms 50300 KB Output is correct
107 Correct 1498 ms 76936 KB Output is correct
108 Correct 1948 ms 132528 KB Output is correct
109 Correct 1442 ms 134404 KB Output is correct