oj.uz

Submission #849571

# Submission time Handle Problem Language Result Execution time Memory
849571 2023-09-15T02:45:22 Z 8pete8 Bridges (APIO19_bridges) C++17
100 / 100
 1227 ms 52212 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<algorithm>
#include<limits.h>
#include<set>
#include<cmath>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<pii,pii>
#define piii pair<pii,int>
#define all(x) x.begin(),x.end()
#define pll pair<ll,ll>
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define double long double
#define int long long
#define mod 1000000007
const int mxn=1e5+5,lg=25;
int root=300;
int pos[mxn+10],ans[mxn+10],pa[mxn+10],sz[mxn+10];
int n,m;
bitset<mxn+10>on,yes;
stack<int>st;
vector<ppii>e;
int find(int u){
    while(u!=pa[u])u=pa[u];
    return u;
}
void re(){for(int i=0;i<=mxn;i++)pa[i]=i,sz[i]=1;}
void merg(int u,int v){
    int a=find(u),b=find(v);
    if(a==b)return;
    if(sz[a]>sz[b]){
        st.push(b);
        pa[b]=a;
        sz[a]+=sz[b];
        return;
    }
    st.push(a);
    pa[a]=b;
    sz[b]+=sz[a];
}
void rollback(int x){
    while(st.size()>x){
        int k=st.top();
        sz[pa[k]]-=sz[k];
        pa[k]=k;
        st.pop();
    }
}
void solve(vector<ppii>q){
    //first type
    //second type
    vector<pii>fq;
    vector<ppii>sq;
    on.reset();
    re();
    int cnt=0;
    for(auto i:q){
        if(i.f.s==-1)fq.pb({i.s.f,i.s.s}),cnt++;//id change
        else sq.pb({{i.s.s,i.s.f},{cnt,i.f.s}});//cost start cnt qryid
    }
    sort(sq.rbegin(),sq.rend());//by cost
    for(auto i:fq)on[i.f]=true;
    sort(e.rbegin(),e.rend());
    for(int i=0;i<e.size();i++)pos[e[i].f.s]=i;
    int cur=0;
    for(auto i:sq){
        while(cur<e.size()&&e[cur].f.f>=i.f.f){
            if(!on[e[cur].f.s])merg(e[cur].s.f,e[cur].s.s);
            cur++;
        }
        int x=st.size();
        yes.reset();
        for(int j=i.s.f-1;j>=0;j--){
            if(fq[j].s>=i.f.f&&(!yes[fq[j].f]))merg(e[pos[fq[j].f]].s.f,e[pos[fq[j].f]].s.s);
            yes[fq[j].f]=true;
        }
        for(int j=i.s.f;j<fq.size();j++)if(!yes[fq[j].f]&&e[pos[fq[j].f]].f.f>=i.f.f)merg(e[pos[fq[j].f]].s.f,e[pos[fq[j].f]].s.s);
        ans[i.s.s]=sz[find(i.f.s)];
        rollback(x);
    }
    for(auto i:fq)e[pos[i.f]].f.f=i.s;
}
int32_t main(){
    fastio
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v,w;cin>>u>>v>>w;
        u--;
        v--;
        e.pb({{w,i},{u,v}});
    }
    int qr;cin>>qr;
    vector<ppii>q(qr);
    root=1000;
    int cnt=0;
    for(int i=0;i<qr;i++){
        //1 id change
        //2 start weight
        cin>>q[i].f.f>>q[i].s.f>>q[i].s.s;
        q[i].f.s=((q[i].f.f==1)?-1:cnt++);
        q[i].s.f--;
    }
    int cur;
    for(int i=0;i<qr;i+=root){
        vector<ppii>cq;
        cur=i;
        while(cur<qr&&cur<i+root)cq.pb(q[cur++]);
        solve(cq);
    }
    for(int i=0;i<cnt;i++)cout<<ans[i]<<'\n';
    return 0;
}

Compilation message

bridges.cpp: In function 'void rollback(long long int)':
bridges.cpp:55:20: warning: comparison of integer expressions of different signedness: 'std::stack<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   55 |     while(st.size()>x){
      |           ~~~~~~~~~^~
bridges.cpp: In function 'void solve(std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >)':
bridges.cpp:77:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<e.size();i++)pos[e[i].f.s]=i;
      |                 ~^~~~~~~~~
bridges.cpp:80:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<std::pair<long long int, long long int>, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         while(cur<e.size()&&e[cur].f.f>=i.f.f){
      |               ~~~^~~~~~~~~
bridges.cpp:90:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int j=i.s.f;j<fq.size();j++)if(!yes[fq[j].f]&&e[pos[fq[j].f]].f.f>=i.f.f)merg(e[pos[fq[j].f]].s.f,e[pos[fq[j].f]].s.s);
      |                         ~^~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 22 ms 3192 KB Output is correct
4 Correct 6 ms 3164 KB Output is correct
5 Correct 20 ms 3160 KB Output is correct
6 Correct 19 ms 3160 KB Output is correct
7 Correct 20 ms 2908 KB Output is correct
8 Correct 18 ms 2908 KB Output is correct
9 Correct 23 ms 2908 KB Output is correct
10 Correct 19 ms 2908 KB Output is correct
11 Correct 18 ms 2908 KB Output is correct
12 Correct 21 ms 2908 KB Output is correct
13 Correct 25 ms 3164 KB Output is correct
14 Correct 25 ms 3156 KB Output is correct
15 Correct 21 ms 2908 KB Output is correct
16 Correct 21 ms 2908 KB Output is correct
17 Correct 20 ms 2904 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 48580 KB Output is correct
2 Correct 696 ms 48508 KB Output is correct
3 Correct 690 ms 48408 KB Output is correct
4 Correct 763 ms 48584 KB Output is correct
5 Correct 791 ms 48344 KB Output is correct
6 Correct 1096 ms 48824 KB Output is correct
7 Correct 1114 ms 48792 KB Output is correct
8 Correct 1073 ms 48604 KB Output is correct
9 Correct 50 ms 6168 KB Output is correct
10 Correct 870 ms 48748 KB Output is correct
11 Correct 757 ms 48536 KB Output is correct
12 Correct 605 ms 49484 KB Output is correct
13 Correct 664 ms 48280 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 33588 KB Output is correct
2 Correct 459 ms 12588 KB Output is correct
3 Correct 633 ms 33948 KB Output is correct
4 Correct 537 ms 33620 KB Output is correct
5 Correct 48 ms 6228 KB Output is correct
6 Correct 611 ms 33736 KB Output is correct
7 Correct 505 ms 33560 KB Output is correct
8 Correct 491 ms 33476 KB Output is correct
9 Correct 426 ms 34252 KB Output is correct
10 Correct 345 ms 34456 KB Output is correct
11 Correct 428 ms 32976 KB Output is correct
12 Correct 362 ms 32860 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 50712 KB Output is correct
2 Correct 48 ms 6228 KB Output is correct
3 Correct 63 ms 6940 KB Output is correct
4 Correct 69 ms 7400 KB Output is correct
5 Correct 587 ms 50812 KB Output is correct
6 Correct 519 ms 51396 KB Output is correct
7 Correct 582 ms 50628 KB Output is correct
8 Correct 271 ms 49208 KB Output is correct
9 Correct 273 ms 48980 KB Output is correct
10 Correct 270 ms 49132 KB Output is correct
11 Correct 415 ms 50360 KB Output is correct
12 Correct 388 ms 50332 KB Output is correct
13 Correct 408 ms 50368 KB Output is correct
14 Correct 607 ms 50632 KB Output is correct
15 Correct 595 ms 51624 KB Output is correct
16 Correct 525 ms 50972 KB Output is correct
17 Correct 560 ms 51116 KB Output is correct
18 Correct 522 ms 52212 KB Output is correct
19 Correct 519 ms 51872 KB Output is correct
20 Correct 484 ms 50992 KB Output is correct
21 Correct 460 ms 51084 KB Output is correct
22 Correct 527 ms 51136 KB Output is correct
23 Correct 502 ms 47300 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 688 ms 48580 KB Output is correct
2 Correct 696 ms 48508 KB Output is correct
3 Correct 690 ms 48408 KB Output is correct
4 Correct 763 ms 48584 KB Output is correct
5 Correct 791 ms 48344 KB Output is correct
6 Correct 1096 ms 48824 KB Output is correct
7 Correct 1114 ms 48792 KB Output is correct
8 Correct 1073 ms 48604 KB Output is correct
9 Correct 50 ms 6168 KB Output is correct
10 Correct 870 ms 48748 KB Output is correct
11 Correct 757 ms 48536 KB Output is correct
12 Correct 605 ms 49484 KB Output is correct
13 Correct 664 ms 48280 KB Output is correct
14 Correct 550 ms 33588 KB Output is correct
15 Correct 459 ms 12588 KB Output is correct
16 Correct 633 ms 33948 KB Output is correct
17 Correct 537 ms 33620 KB Output is correct
18 Correct 48 ms 6228 KB Output is correct
19 Correct 611 ms 33736 KB Output is correct
20 Correct 505 ms 33560 KB Output is correct
21 Correct 491 ms 33476 KB Output is correct
22 Correct 426 ms 34252 KB Output is correct
23 Correct 345 ms 34456 KB Output is correct
24 Correct 428 ms 32976 KB Output is correct
25 Correct 362 ms 32860 KB Output is correct
26 Correct 732 ms 48952 KB Output is correct
27 Correct 830 ms 48808 KB Output is correct
28 Correct 715 ms 48568 KB Output is correct
29 Correct 547 ms 48600 KB Output is correct
30 Correct 866 ms 48628 KB Output is correct
31 Correct 849 ms 48588 KB Output is correct
32 Correct 853 ms 48440 KB Output is correct
33 Correct 705 ms 48328 KB Output is correct
34 Correct 751 ms 48448 KB Output is correct
35 Correct 732 ms 48644 KB Output is correct
36 Correct 594 ms 48612 KB Output is correct
37 Correct 555 ms 48228 KB Output is correct
38 Correct 543 ms 48180 KB Output is correct
39 Correct 444 ms 48916 KB Output is correct
40 Correct 486 ms 48836 KB Output is correct
41 Correct 462 ms 48820 KB Output is correct
42 Correct 464 ms 46820 KB Output is correct
43 Correct 423 ms 46792 KB Output is correct
44 Correct 436 ms 46672 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2804 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 22 ms 3192 KB Output is correct
4 Correct 6 ms 3164 KB Output is correct
5 Correct 20 ms 3160 KB Output is correct
6 Correct 19 ms 3160 KB Output is correct
7 Correct 20 ms 2908 KB Output is correct
8 Correct 18 ms 2908 KB Output is correct
9 Correct 23 ms 2908 KB Output is correct
10 Correct 19 ms 2908 KB Output is correct
11 Correct 18 ms 2908 KB Output is correct
12 Correct 21 ms 2908 KB Output is correct
13 Correct 25 ms 3164 KB Output is correct
14 Correct 25 ms 3156 KB Output is correct
15 Correct 21 ms 2908 KB Output is correct
16 Correct 21 ms 2908 KB Output is correct
17 Correct 20 ms 2904 KB Output is correct
18 Correct 688 ms 48580 KB Output is correct
19 Correct 696 ms 48508 KB Output is correct
20 Correct 690 ms 48408 KB Output is correct
21 Correct 763 ms 48584 KB Output is correct
22 Correct 791 ms 48344 KB Output is correct
23 Correct 1096 ms 48824 KB Output is correct
24 Correct 1114 ms 48792 KB Output is correct
25 Correct 1073 ms 48604 KB Output is correct
26 Correct 50 ms 6168 KB Output is correct
27 Correct 870 ms 48748 KB Output is correct
28 Correct 757 ms 48536 KB Output is correct
29 Correct 605 ms 49484 KB Output is correct
30 Correct 664 ms 48280 KB Output is correct
31 Correct 550 ms 33588 KB Output is correct
32 Correct 459 ms 12588 KB Output is correct
33 Correct 633 ms 33948 KB Output is correct
34 Correct 537 ms 33620 KB Output is correct
35 Correct 48 ms 6228 KB Output is correct
36 Correct 611 ms 33736 KB Output is correct
37 Correct 505 ms 33560 KB Output is correct
38 Correct 491 ms 33476 KB Output is correct
39 Correct 426 ms 34252 KB Output is correct
40 Correct 345 ms 34456 KB Output is correct
41 Correct 428 ms 32976 KB Output is correct
42 Correct 362 ms 32860 KB Output is correct
43 Correct 527 ms 50712 KB Output is correct
44 Correct 48 ms 6228 KB Output is correct
45 Correct 63 ms 6940 KB Output is correct
46 Correct 69 ms 7400 KB Output is correct
47 Correct 587 ms 50812 KB Output is correct
48 Correct 519 ms 51396 KB Output is correct
49 Correct 582 ms 50628 KB Output is correct
50 Correct 271 ms 49208 KB Output is correct
51 Correct 273 ms 48980 KB Output is correct
52 Correct 270 ms 49132 KB Output is correct
53 Correct 415 ms 50360 KB Output is correct
54 Correct 388 ms 50332 KB Output is correct
55 Correct 408 ms 50368 KB Output is correct
56 Correct 607 ms 50632 KB Output is correct
57 Correct 595 ms 51624 KB Output is correct
58 Correct 525 ms 50972 KB Output is correct
59 Correct 560 ms 51116 KB Output is correct
60 Correct 522 ms 52212 KB Output is correct
61 Correct 519 ms 51872 KB Output is correct
62 Correct 484 ms 50992 KB Output is correct
63 Correct 460 ms 51084 KB Output is correct
64 Correct 527 ms 51136 KB Output is correct
65 Correct 502 ms 47300 KB Output is correct
66 Correct 732 ms 48952 KB Output is correct
67 Correct 830 ms 48808 KB Output is correct
68 Correct 715 ms 48568 KB Output is correct
69 Correct 547 ms 48600 KB Output is correct
70 Correct 866 ms 48628 KB Output is correct
71 Correct 849 ms 48588 KB Output is correct
72 Correct 853 ms 48440 KB Output is correct
73 Correct 705 ms 48328 KB Output is correct
74 Correct 751 ms 48448 KB Output is correct
75 Correct 732 ms 48644 KB Output is correct
76 Correct 594 ms 48612 KB Output is correct
77 Correct 555 ms 48228 KB Output is correct
78 Correct 543 ms 48180 KB Output is correct
79 Correct 444 ms 48916 KB Output is correct
80 Correct 486 ms 48836 KB Output is correct
81 Correct 462 ms 48820 KB Output is correct
82 Correct 464 ms 46820 KB Output is correct
83 Correct 423 ms 46792 KB Output is correct
84 Correct 436 ms 46672 KB Output is correct
85 Correct 1104 ms 50588 KB Output is correct
86 Correct 109 ms 7044 KB Output is correct
87 Correct 88 ms 7616 KB Output is correct
88 Correct 1227 ms 50360 KB Output is correct
89 Correct 1029 ms 50140 KB Output is correct
90 Correct 1163 ms 50972 KB Output is correct
91 Correct 805 ms 48312 KB Output is correct
92 Correct 768 ms 48680 KB Output is correct
93 Correct 1109 ms 48572 KB Output is correct
94 Correct 904 ms 50696 KB Output is correct
95 Correct 983 ms 51220 KB Output is correct
96 Correct 986 ms 50008 KB Output is correct
97 Correct 972 ms 50388 KB Output is correct
98 Correct 992 ms 50588 KB Output is correct
99 Correct 1131 ms 50712 KB Output is correct
100 Correct 1089 ms 50612 KB Output is correct
101 Correct 1085 ms 50888 KB Output is correct
102 Correct 1093 ms 50992 KB Output is correct
103 Correct 1041 ms 50216 KB Output is correct
104 Correct 1105 ms 51292 KB Output is correct
105 Correct 782 ms 50612 KB Output is correct
106 Correct 740 ms 51140 KB Output is correct
107 Correct 808 ms 51708 KB Output is correct
108 Correct 1104 ms 49936 KB Output is correct
109 Correct 1034 ms 46040 KB Output is correct