oj.uz

Submission #755173

# Submission time Handle Problem Language Result Execution time Memory
755173 2023-06-09T13:22:46 Z Ahmed57 Bridges (APIO19_bridges) C++17
100 / 100
 2693 ms 153304 KB 
#include <bits/stdc++.h>
using namespace std;
int t[100001],x[100001],z[100001];
int u[100001],v[100001],cost[100001];
bool comp1(int a,int b){
    return z[a]>z[b];
}
bool comp2(int a,int b){
    return cost[a]>cost[b];
}
int pr[50001];
int gs[50001];

int findleader(int x){
    if(pr[x]==x){
        return x;
    }
    return findleader(pr[x]);
}
bool samegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    return led1==led2;
}
stack<int> st;
void mergegroup(int x,int y){
    int led1 = findleader(x);
    int led2 = findleader(y);
    if(led1==led2)return;
    if(gs[led1]>gs[led2]){
        pr[led2]=led1;
        gs[led1]+=gs[led2];
        st.push(led2);
    }else{
        pr[led1]=led2;
        gs[led2]+=gs[led1];
        st.push(led1);
    }
}
void rollback(int sx){
    while(sx--){
        gs[findleader(st.top())]-=gs[st.top()];
        pr[st.top()] = st.top();
        st.pop();
    }
}
int get(int x){
    int led = findleader(x);
    return gs[led];
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=m;i++){
        cin>>u[i]>>v[i]>>cost[i];
    }
    int q;cin>>q;
    int ans[q+1];
    memset(ans,-1,sizeof ans);
    vector<int> join[q+1];
    for(int i =1;i<=q;i++){
        cin>>t[i]>>x[i]>>z[i];
    }
    for(int l = 1;l<=q;l+=1000){
        for(int i = 1;i<=n;i++){
            pr[i] = i , gs[i] = 1;
        }
        int r = min(q+1,l+1000);
        bool change[m+1] = {0};
        vector<int> ques,upd;
        for(int i = l;i<r;i++){
            if(t[i]==1){
                change[x[i]] = 1;
                upd.push_back(x[i]);
            }else ques.push_back(i);
        }
        sort(ques.begin(),ques.end(),comp1);
        vector<int> unchanged;
        for(int i = 1;i<=m;i++){
            if(!change[i])unchanged.push_back(i);
        }
        sort(unchanged.begin(),unchanged.end(),comp2);
        for(int i = l;i<r;i++){
            if(t[i]==1){
                cost[x[i]] = z[i];
            }else{
                join[i].clear();
                for(auto j:upd){
                    if(cost[j]>=z[i]){
                        join[i].push_back(j);
                    }
                }
            }
        }
        int ptr = 0;
        for(auto i:ques){
            while(ptr<unchanged.size()&&cost[unchanged[ptr]]>=z[i]){
                mergegroup(u[unchanged[ptr]],v[unchanged[ptr]]);
                ptr++;
            }
            int sx = 0;
            for(auto j:join[i]){
                sx++;
                if(samegroup(u[j],v[j]))sx--;
                mergegroup(u[j],v[j]);
            }
            ans[i] = get(x[i]);
            rollback(sx);
        }
    }
    for(int i = 1;i<=q;i++){
        if(ans[i]!=-1)cout<<ans[i]<<"\n";
    }
    return 0;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             while(ptr<unchanged.size()&&cost[unchanged[ptr]]>=z[i]){
      |                   ~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 42 ms 7332 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 45 ms 8140 KB Output is correct
6 Correct 33 ms 8268 KB Output is correct
7 Correct 42 ms 8344 KB Output is correct
8 Correct 46 ms 6732 KB Output is correct
9 Correct 70 ms 12692 KB Output is correct
10 Correct 50 ms 7584 KB Output is correct
11 Correct 43 ms 7372 KB Output is correct
12 Correct 55 ms 9828 KB Output is correct
13 Correct 57 ms 7888 KB Output is correct
14 Correct 54 ms 7116 KB Output is correct
15 Correct 63 ms 7988 KB Output is correct
16 Correct 55 ms 10848 KB Output is correct
17 Correct 50 ms 9988 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1561 ms 93448 KB Output is correct
2 Correct 1639 ms 95588 KB Output is correct
3 Correct 1630 ms 95872 KB Output is correct
4 Correct 1653 ms 95372 KB Output is correct
5 Correct 1574 ms 95912 KB Output is correct
6 Correct 2510 ms 153304 KB Output is correct
7 Correct 2685 ms 149876 KB Output is correct
8 Correct 2693 ms 149712 KB Output is correct
9 Correct 39 ms 5716 KB Output is correct
10 Correct 1534 ms 120180 KB Output is correct
11 Correct 1385 ms 119324 KB Output is correct
12 Correct 1452 ms 75376 KB Output is correct
13 Correct 1413 ms 68496 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1262 ms 86336 KB Output is correct
2 Correct 980 ms 102536 KB Output is correct
3 Correct 1534 ms 115948 KB Output is correct
4 Correct 1247 ms 87728 KB Output is correct
5 Correct 36 ms 5708 KB Output is correct
6 Correct 1479 ms 107584 KB Output is correct
7 Correct 1157 ms 79532 KB Output is correct
8 Correct 1034 ms 63816 KB Output is correct
9 Correct 829 ms 55696 KB Output is correct
10 Correct 744 ms 44156 KB Output is correct
11 Correct 898 ms 52920 KB Output is correct
12 Correct 761 ms 42588 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1763 ms 27876 KB Output is correct
2 Correct 36 ms 5796 KB Output is correct
3 Correct 192 ms 4736 KB Output is correct
4 Correct 90 ms 4928 KB Output is correct
5 Correct 918 ms 29548 KB Output is correct
6 Correct 1650 ms 31020 KB Output is correct
7 Correct 868 ms 29488 KB Output is correct
8 Correct 821 ms 29020 KB Output is correct
9 Correct 802 ms 28988 KB Output is correct
10 Correct 798 ms 28944 KB Output is correct
11 Correct 1235 ms 30304 KB Output is correct
12 Correct 1241 ms 30480 KB Output is correct
13 Correct 1209 ms 30348 KB Output is correct
14 Correct 815 ms 29492 KB Output is correct
15 Correct 804 ms 29500 KB Output is correct
16 Correct 1646 ms 31252 KB Output is correct
17 Correct 1664 ms 31208 KB Output is correct
18 Correct 1668 ms 31544 KB Output is correct
19 Correct 1629 ms 31488 KB Output is correct
20 Correct 1356 ms 30804 KB Output is correct
21 Correct 1337 ms 30612 KB Output is correct
22 Correct 1585 ms 30592 KB Output is correct
23 Correct 887 ms 27224 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1561 ms 93448 KB Output is correct
2 Correct 1639 ms 95588 KB Output is correct
3 Correct 1630 ms 95872 KB Output is correct
4 Correct 1653 ms 95372 KB Output is correct
5 Correct 1574 ms 95912 KB Output is correct
6 Correct 2510 ms 153304 KB Output is correct
7 Correct 2685 ms 149876 KB Output is correct
8 Correct 2693 ms 149712 KB Output is correct
9 Correct 39 ms 5716 KB Output is correct
10 Correct 1534 ms 120180 KB Output is correct
11 Correct 1385 ms 119324 KB Output is correct
12 Correct 1452 ms 75376 KB Output is correct
13 Correct 1413 ms 68496 KB Output is correct
14 Correct 1262 ms 86336 KB Output is correct
15 Correct 980 ms 102536 KB Output is correct
16 Correct 1534 ms 115948 KB Output is correct
17 Correct 1247 ms 87728 KB Output is correct
18 Correct 36 ms 5708 KB Output is correct
19 Correct 1479 ms 107584 KB Output is correct
20 Correct 1157 ms 79532 KB Output is correct
21 Correct 1034 ms 63816 KB Output is correct
22 Correct 829 ms 55696 KB Output is correct
23 Correct 744 ms 44156 KB Output is correct
24 Correct 898 ms 52920 KB Output is correct
25 Correct 761 ms 42588 KB Output is correct
26 Correct 1571 ms 95632 KB Output is correct
27 Correct 1949 ms 124808 KB Output is correct
28 Correct 1565 ms 93856 KB Output is correct
29 Correct 1081 ms 50888 KB Output is correct
30 Correct 1890 ms 111168 KB Output is correct
31 Correct 1856 ms 113684 KB Output is correct
32 Correct 1875 ms 114076 KB Output is correct
33 Correct 1580 ms 94104 KB Output is correct
34 Correct 1575 ms 94392 KB Output is correct
35 Correct 1569 ms 94796 KB Output is correct
36 Correct 1164 ms 57720 KB Output is correct
37 Correct 1160 ms 56552 KB Output is correct
38 Correct 1113 ms 54964 KB Output is correct
39 Correct 906 ms 41172 KB Output is correct
40 Correct 924 ms 40324 KB Output is correct
41 Correct 914 ms 39868 KB Output is correct
42 Correct 904 ms 38584 KB Output is correct
43 Correct 894 ms 38068 KB Output is correct
44 Correct 888 ms 37476 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 42 ms 7332 KB Output is correct
4 Correct 4 ms 724 KB Output is correct
5 Correct 45 ms 8140 KB Output is correct
6 Correct 33 ms 8268 KB Output is correct
7 Correct 42 ms 8344 KB Output is correct
8 Correct 46 ms 6732 KB Output is correct
9 Correct 70 ms 12692 KB Output is correct
10 Correct 50 ms 7584 KB Output is correct
11 Correct 43 ms 7372 KB Output is correct
12 Correct 55 ms 9828 KB Output is correct
13 Correct 57 ms 7888 KB Output is correct
14 Correct 54 ms 7116 KB Output is correct
15 Correct 63 ms 7988 KB Output is correct
16 Correct 55 ms 10848 KB Output is correct
17 Correct 50 ms 9988 KB Output is correct
18 Correct 1561 ms 93448 KB Output is correct
19 Correct 1639 ms 95588 KB Output is correct
20 Correct 1630 ms 95872 KB Output is correct
21 Correct 1653 ms 95372 KB Output is correct
22 Correct 1574 ms 95912 KB Output is correct
23 Correct 2510 ms 153304 KB Output is correct
24 Correct 2685 ms 149876 KB Output is correct
25 Correct 2693 ms 149712 KB Output is correct
26 Correct 39 ms 5716 KB Output is correct
27 Correct 1534 ms 120180 KB Output is correct
28 Correct 1385 ms 119324 KB Output is correct
29 Correct 1452 ms 75376 KB Output is correct
30 Correct 1413 ms 68496 KB Output is correct
31 Correct 1262 ms 86336 KB Output is correct
32 Correct 980 ms 102536 KB Output is correct
33 Correct 1534 ms 115948 KB Output is correct
34 Correct 1247 ms 87728 KB Output is correct
35 Correct 36 ms 5708 KB Output is correct
36 Correct 1479 ms 107584 KB Output is correct
37 Correct 1157 ms 79532 KB Output is correct
38 Correct 1034 ms 63816 KB Output is correct
39 Correct 829 ms 55696 KB Output is correct
40 Correct 744 ms 44156 KB Output is correct
41 Correct 898 ms 52920 KB Output is correct
42 Correct 761 ms 42588 KB Output is correct
43 Correct 1763 ms 27876 KB Output is correct
44 Correct 36 ms 5796 KB Output is correct
45 Correct 192 ms 4736 KB Output is correct
46 Correct 90 ms 4928 KB Output is correct
47 Correct 918 ms 29548 KB Output is correct
48 Correct 1650 ms 31020 KB Output is correct
49 Correct 868 ms 29488 KB Output is correct
50 Correct 821 ms 29020 KB Output is correct
51 Correct 802 ms 28988 KB Output is correct
52 Correct 798 ms 28944 KB Output is correct
53 Correct 1235 ms 30304 KB Output is correct
54 Correct 1241 ms 30480 KB Output is correct
55 Correct 1209 ms 30348 KB Output is correct
56 Correct 815 ms 29492 KB Output is correct
57 Correct 804 ms 29500 KB Output is correct
58 Correct 1646 ms 31252 KB Output is correct
59 Correct 1664 ms 31208 KB Output is correct
60 Correct 1668 ms 31544 KB Output is correct
61 Correct 1629 ms 31488 KB Output is correct
62 Correct 1356 ms 30804 KB Output is correct
63 Correct 1337 ms 30612 KB Output is correct
64 Correct 1585 ms 30592 KB Output is correct
65 Correct 887 ms 27224 KB Output is correct
66 Correct 1571 ms 95632 KB Output is correct
67 Correct 1949 ms 124808 KB Output is correct
68 Correct 1565 ms 93856 KB Output is correct
69 Correct 1081 ms 50888 KB Output is correct
70 Correct 1890 ms 111168 KB Output is correct
71 Correct 1856 ms 113684 KB Output is correct
72 Correct 1875 ms 114076 KB Output is correct
73 Correct 1580 ms 94104 KB Output is correct
74 Correct 1575 ms 94392 KB Output is correct
75 Correct 1569 ms 94796 KB Output is correct
76 Correct 1164 ms 57720 KB Output is correct
77 Correct 1160 ms 56552 KB Output is correct
78 Correct 1113 ms 54964 KB Output is correct
79 Correct 906 ms 41172 KB Output is correct
80 Correct 924 ms 40324 KB Output is correct
81 Correct 914 ms 39868 KB Output is correct
82 Correct 904 ms 38584 KB Output is correct
83 Correct 894 ms 38068 KB Output is correct
84 Correct 888 ms 37476 KB Output is correct
85 Correct 2212 ms 97632 KB Output is correct
86 Correct 207 ms 10932 KB Output is correct
87 Correct 150 ms 15416 KB Output is correct
88 Correct 1411 ms 109680 KB Output is correct
89 Correct 2141 ms 96200 KB Output is correct
90 Correct 1389 ms 118000 KB Output is correct
91 Correct 1608 ms 95620 KB Output is correct
92 Correct 1628 ms 95356 KB Output is correct
93 Correct 2412 ms 133228 KB Output is correct
94 Correct 1914 ms 96860 KB Output is correct
95 Correct 1926 ms 96868 KB Output is correct
96 Correct 2388 ms 137660 KB Output is correct
97 Correct 1102 ms 62244 KB Output is correct
98 Correct 1118 ms 58932 KB Output is correct
99 Correct 2254 ms 98716 KB Output is correct
100 Correct 2215 ms 97580 KB Output is correct
101 Correct 2297 ms 97784 KB Output is correct
102 Correct 2260 ms 97728 KB Output is correct
103 Correct 2626 ms 142996 KB Output is correct
104 Correct 2613 ms 142556 KB Output is correct
105 Correct 1836 ms 70420 KB Output is correct
106 Correct 1489 ms 50364 KB Output is correct
107 Correct 1750 ms 76844 KB Output is correct
108 Correct 2401 ms 132572 KB Output is correct
109 Correct 1817 ms 134408 KB Output is correct