Submission #555820

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
555820	2022-05-01T15:39:09 Z	shahriarkhan	Bridges (APIO19_bridges)	C++14	100 / 100	2474 ms	9408 KB

bridges

#include<bits/stdc++.h>
using namespace std ;

const int MX = 1e5 + 5 , block = 800 ;

struct query
{
    int type = 0 , vertice = 0 , edge = 0 , weight = 0 , idx = 0 ;
};

bool cmp(pair<int,int> &a , pair<int,int> &b)
{
    if(a.first!=b.first) return a.first > b.first ;
    return a.second > b.second ;
}

bool cmp1(query &a , query &b)
{
    if(a.weight!=b.weight) return a.weight > b.weight ;
    return a.idx < b.idx ;
}

vector<query> temp ;

vector<pair<int,int> > edges , edg ;

int ans[MX] , typ[MX] , val[MX] , vis[MX] , cur[MX] , temp_siz , n , m ;

struct dsu_rollback
{
    int u = 0 , v = 0 , siz_u = 0 , siz_v = 0 ;
};

struct dsu
{
    vector<int> par , siz ;
    stack<dsu_rollback> s ;
    void init(int n)
    {
        par = vector<int> (n+5,0) ;
        siz = vector<int> (n+5,0) ;
        for(int i = 1 ; i <= n ; ++i)
        {
            par[i] = i ;
            siz[i] = 1 ;
        }
    }
    int find_root(int a)
    {
        if(par[a]==a) return a ;
        return find_root(par[a]) ;
    }
    int union_edge(int a , int b)
    {
        int root_a = find_root(a) , root_b = find_root(b) ;
        if(root_a==root_b) return 0 ;
        if(siz[root_b]>siz[root_a]) swap(root_a,root_b) ;
        s.push({root_a,root_b,siz[root_a],siz[root_b]}) ;
        par[root_b] = root_a ;
        siz[root_a] += siz[root_b] ;
        return 1 ;
    }
    void rollback()
    {
        if(s.empty()) return ;
        dsu_rollback cur = s.top() ;
        s.pop() ;
        par[cur.u] = cur.u ;
        siz[cur.u] = cur.siz_u ;
        par[cur.v] = cur.v ;
        siz[cur.v] = cur.siz_v ;
    }
    int find_siz(int x)
    {
        return siz[find_root(x)] ;
    }
};

void process()
{
    dsu D ;
    D.init(n) ;
    vector<query> upd , out ;
    vector<int> unused ;
    unused.reserve(block) ;
    upd.reserve(block) ;
    out.reserve(block) ;
    for(query &q : temp)
    {
        if(q.type==1)
        {
            vis[q.edge] = 1 ;
            upd.emplace_back(q) ;
        }
        else out.emplace_back(q) ;
    }
    for(int i = 1 ; i <= m ; ++i)
    {
        if(vis[i]) unused.emplace_back(i) ;
    }
    sort(out.begin(),out.end(),cmp1) ;
    sort(edg.begin(),edg.end(),cmp) ;
    int cr = 0 ;
    for(query &q : out)
    {
        while((cr<m) && (edg[cr].first>=q.weight))
        {
            if(!vis[edg[cr].second]) D.union_edge(edges[edg[cr].second].first,edges[edg[cr].second].second) ;
            ++cr ;
        }
        int rollback = 0 ;
        for(query &p : upd)
        {
            if(p.idx>q.idx) break ;
            cur[p.edge] = p.weight ;
        }
        for(query &p : upd)
        {
            if(p.idx>q.idx) break ;
            if(cur[p.edge]>=q.weight)
            {
                rollback += D.union_edge(edges[p.edge].first,edges[p.edge].second) ;
                cur[p.edge] = -1 ;
            }
        }
        for(int &i : unused)
        {
            if(cur[i]) continue ;
            if(val[i]>=q.weight)
            {
                rollback += D.union_edge(edges[i].first,edges[i].second) ;
                cur[i] = -1 ;
            }
        }
        ans[q.idx] = D.find_siz(q.vertice) ;
        while(rollback)
        {
            D.rollback() ;
            --rollback ;
        }
        for(int &i : unused)
        {
            cur[i] = 0 ;
        }
    }
    for(query &q : upd)
    {
        val[q.edge] = q.weight ;
    }
    for(int i = 0 ; i < m ; ++i)
    {
        if(vis[edg[i].second])
        {
            edg[i].first = val[edg[i].second] , vis[edg[i].second] = 0 , cur[i] = 0 ;
        }
    }
    temp.clear() , temp_siz = 0 ;
}

int main()
{
    scanf("%d%d",&n,&m) ;
    edges.reserve(MX) ;
    edges.emplace_back(make_pair(0,0)) ;
    temp.reserve(block) ;
    for(int i = 1 ; i <= m ; ++i)
    {
        int a , b , d ;
        scanf("%d%d%d",&a,&b,&d) ;
        edges.emplace_back(make_pair(a,b)) ;
        val[i] = d ;
        edg.emplace_back(make_pair(val[i],i)) ;
    }
    int q ;
    scanf("%d",&q) ;
    for(int i = 1 ; i <= q ; ++i)
    {
        int type ;
        scanf("%d",&type) ;
        typ[i] = type ;
        if(type==1)
        {
            int b , r ;
            scanf("%d%d",&b,&r) ;
            query f = {1,0,b,r,i} ;
            temp.emplace_back(f) , ++temp_siz ;
        }
        else
        {
            int s , w ;
            scanf("%d%d",&s,&w) ;
            query f = {2,s,0,w,i} ;
            temp.emplace_back(f) , ++temp_siz ;
        }
        if(temp_siz==block) process() ;
    }
    if(temp_siz) process() ;
    for(int i = 1 ; i <= q ; ++i)
    {
        if(typ[i]==2) printf("%d\n",ans[i]) ;
    }
    return 0 ;
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:162:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     scanf("%d%d",&n,&m) ;
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:169:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         scanf("%d%d%d",&a,&b,&d) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~
bridges.cpp:175:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |     scanf("%d",&q) ;
      |     ~~~~~^~~~~~~~~
bridges.cpp:179:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |         scanf("%d",&type) ;
      |         ~~~~~^~~~~~~~~~~~
bridges.cpp:184:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |             scanf("%d%d",&b,&r) ;
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:191:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  191 |             scanf("%d%d",&s,&w) ;
      |             ~~~~~^~~~~~~~~~~~~~

Subtask #1

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	29 ms	428 KB	Output is correct
4	Correct	4 ms	468 KB	Output is correct
5	Correct	14 ms	468 KB	Output is correct
6	Correct	14 ms	416 KB	Output is correct
7	Correct	18 ms	468 KB	Output is correct
8	Correct	17 ms	420 KB	Output is correct
9	Correct	19 ms	412 KB	Output is correct
10	Correct	17 ms	468 KB	Output is correct
11	Correct	17 ms	468 KB	Output is correct
12	Correct	20 ms	468 KB	Output is correct
13	Correct	24 ms	440 KB	Output is correct
14	Correct	22 ms	448 KB	Output is correct
15	Correct	19 ms	460 KB	Output is correct
16	Correct	18 ms	404 KB	Output is correct
17	Correct	18 ms	444 KB	Output is correct

Subtask #2

16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1469 ms	3944 KB	Output is correct
2	Correct	1439 ms	3824 KB	Output is correct
3	Correct	1483 ms	4048 KB	Output is correct
4	Correct	1479 ms	3780 KB	Output is correct
5	Correct	1469 ms	3824 KB	Output is correct
6	Correct	1948 ms	3992 KB	Output is correct
7	Correct	1963 ms	3988 KB	Output is correct
8	Correct	1990 ms	4012 KB	Output is correct
9	Correct	44 ms	1228 KB	Output is correct
10	Correct	1391 ms	3860 KB	Output is correct
11	Correct	1318 ms	3788 KB	Output is correct
12	Correct	1234 ms	4136 KB	Output is correct
13	Correct	1209 ms	3840 KB	Output is correct

Subtask #3

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1103 ms	3268 KB	Output is correct
2	Correct	773 ms	1928 KB	Output is correct
3	Correct	1235 ms	3068 KB	Output is correct
4	Correct	1085 ms	3016 KB	Output is correct
5	Correct	42 ms	1252 KB	Output is correct
6	Correct	1207 ms	2980 KB	Output is correct
7	Correct	1049 ms	2940 KB	Output is correct
8	Correct	949 ms	2928 KB	Output is correct
9	Correct	761 ms	3212 KB	Output is correct
10	Correct	708 ms	3268 KB	Output is correct
11	Correct	766 ms	2844 KB	Output is correct
12	Correct	688 ms	2940 KB	Output is correct

Subtask #4

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1377 ms	4700 KB	Output is correct
2	Correct	44 ms	2668 KB	Output is correct
3	Correct	158 ms	4424 KB	Output is correct
4	Correct	141 ms	4560 KB	Output is correct
5	Correct	1140 ms	7108 KB	Output is correct
6	Correct	1385 ms	8652 KB	Output is correct
7	Correct	1142 ms	7068 KB	Output is correct
8	Correct	740 ms	6048 KB	Output is correct
9	Correct	742 ms	6224 KB	Output is correct
10	Correct	755 ms	5984 KB	Output is correct
11	Correct	1024 ms	7532 KB	Output is correct
12	Correct	1004 ms	7504 KB	Output is correct
13	Correct	1016 ms	7300 KB	Output is correct
14	Correct	1130 ms	7200 KB	Output is correct
15	Correct	1139 ms	7304 KB	Output is correct
16	Correct	1360 ms	8472 KB	Output is correct
17	Correct	1350 ms	8400 KB	Output is correct
18	Correct	1427 ms	8496 KB	Output is correct
19	Correct	1382 ms	8552 KB	Output is correct
20	Correct	1204 ms	7660 KB	Output is correct
21	Correct	1182 ms	7844 KB	Output is correct
22	Correct	1326 ms	8280 KB	Output is correct
23	Correct	1077 ms	6436 KB	Output is correct

Subtask #5

13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1469 ms	3944 KB	Output is correct
2	Correct	1439 ms	3824 KB	Output is correct
3	Correct	1483 ms	4048 KB	Output is correct
4	Correct	1479 ms	3780 KB	Output is correct
5	Correct	1469 ms	3824 KB	Output is correct
6	Correct	1948 ms	3992 KB	Output is correct
7	Correct	1963 ms	3988 KB	Output is correct
8	Correct	1990 ms	4012 KB	Output is correct
9	Correct	44 ms	1228 KB	Output is correct
10	Correct	1391 ms	3860 KB	Output is correct
11	Correct	1318 ms	3788 KB	Output is correct
12	Correct	1234 ms	4136 KB	Output is correct
13	Correct	1209 ms	3840 KB	Output is correct
14	Correct	1103 ms	3268 KB	Output is correct
15	Correct	773 ms	1928 KB	Output is correct
16	Correct	1235 ms	3068 KB	Output is correct
17	Correct	1085 ms	3016 KB	Output is correct
18	Correct	42 ms	1252 KB	Output is correct
19	Correct	1207 ms	2980 KB	Output is correct
20	Correct	1049 ms	2940 KB	Output is correct
21	Correct	949 ms	2928 KB	Output is correct
22	Correct	761 ms	3212 KB	Output is correct
23	Correct	708 ms	3268 KB	Output is correct
24	Correct	766 ms	2844 KB	Output is correct
25	Correct	688 ms	2940 KB	Output is correct
26	Correct	1454 ms	4064 KB	Output is correct
27	Correct	1786 ms	3828 KB	Output is correct
28	Correct	1532 ms	4036 KB	Output is correct
29	Correct	1224 ms	3748 KB	Output is correct
30	Correct	1702 ms	3868 KB	Output is correct
31	Correct	1722 ms	3984 KB	Output is correct
32	Correct	1762 ms	3880 KB	Output is correct
33	Correct	1534 ms	3948 KB	Output is correct
34	Correct	1528 ms	4024 KB	Output is correct
35	Correct	1517 ms	3840 KB	Output is correct
36	Correct	1288 ms	3908 KB	Output is correct
37	Correct	1231 ms	3876 KB	Output is correct
38	Correct	1224 ms	3928 KB	Output is correct
39	Correct	1033 ms	3872 KB	Output is correct
40	Correct	1039 ms	3948 KB	Output is correct
41	Correct	1029 ms	4036 KB	Output is correct
42	Correct	978 ms	3736 KB	Output is correct
43	Correct	984 ms	3932 KB	Output is correct
44	Correct	962 ms	3800 KB	Output is correct

Subtask #6

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	29 ms	428 KB	Output is correct
4	Correct	4 ms	468 KB	Output is correct
5	Correct	14 ms	468 KB	Output is correct
6	Correct	14 ms	416 KB	Output is correct
7	Correct	18 ms	468 KB	Output is correct
8	Correct	17 ms	420 KB	Output is correct
9	Correct	19 ms	412 KB	Output is correct
10	Correct	17 ms	468 KB	Output is correct
11	Correct	17 ms	468 KB	Output is correct
12	Correct	20 ms	468 KB	Output is correct
13	Correct	24 ms	440 KB	Output is correct
14	Correct	22 ms	448 KB	Output is correct
15	Correct	19 ms	460 KB	Output is correct
16	Correct	18 ms	404 KB	Output is correct
17	Correct	18 ms	444 KB	Output is correct
18	Correct	1469 ms	3944 KB	Output is correct
19	Correct	1439 ms	3824 KB	Output is correct
20	Correct	1483 ms	4048 KB	Output is correct
21	Correct	1479 ms	3780 KB	Output is correct
22	Correct	1469 ms	3824 KB	Output is correct
23	Correct	1948 ms	3992 KB	Output is correct
24	Correct	1963 ms	3988 KB	Output is correct
25	Correct	1990 ms	4012 KB	Output is correct
26	Correct	44 ms	1228 KB	Output is correct
27	Correct	1391 ms	3860 KB	Output is correct
28	Correct	1318 ms	3788 KB	Output is correct
29	Correct	1234 ms	4136 KB	Output is correct
30	Correct	1209 ms	3840 KB	Output is correct
31	Correct	1103 ms	3268 KB	Output is correct
32	Correct	773 ms	1928 KB	Output is correct
33	Correct	1235 ms	3068 KB	Output is correct
34	Correct	1085 ms	3016 KB	Output is correct
35	Correct	42 ms	1252 KB	Output is correct
36	Correct	1207 ms	2980 KB	Output is correct
37	Correct	1049 ms	2940 KB	Output is correct
38	Correct	949 ms	2928 KB	Output is correct
39	Correct	761 ms	3212 KB	Output is correct
40	Correct	708 ms	3268 KB	Output is correct
41	Correct	766 ms	2844 KB	Output is correct
42	Correct	688 ms	2940 KB	Output is correct
43	Correct	1377 ms	4700 KB	Output is correct
44	Correct	44 ms	2668 KB	Output is correct
45	Correct	158 ms	4424 KB	Output is correct
46	Correct	141 ms	4560 KB	Output is correct
47	Correct	1140 ms	7108 KB	Output is correct
48	Correct	1385 ms	8652 KB	Output is correct
49	Correct	1142 ms	7068 KB	Output is correct
50	Correct	740 ms	6048 KB	Output is correct
51	Correct	742 ms	6224 KB	Output is correct
52	Correct	755 ms	5984 KB	Output is correct
53	Correct	1024 ms	7532 KB	Output is correct
54	Correct	1004 ms	7504 KB	Output is correct
55	Correct	1016 ms	7300 KB	Output is correct
56	Correct	1130 ms	7200 KB	Output is correct
57	Correct	1139 ms	7304 KB	Output is correct
58	Correct	1360 ms	8472 KB	Output is correct
59	Correct	1350 ms	8400 KB	Output is correct
60	Correct	1427 ms	8496 KB	Output is correct
61	Correct	1382 ms	8552 KB	Output is correct
62	Correct	1204 ms	7660 KB	Output is correct
63	Correct	1182 ms	7844 KB	Output is correct
64	Correct	1326 ms	8280 KB	Output is correct
65	Correct	1077 ms	6436 KB	Output is correct
66	Correct	1454 ms	4064 KB	Output is correct
67	Correct	1786 ms	3828 KB	Output is correct
68	Correct	1532 ms	4036 KB	Output is correct
69	Correct	1224 ms	3748 KB	Output is correct
70	Correct	1702 ms	3868 KB	Output is correct
71	Correct	1722 ms	3984 KB	Output is correct
72	Correct	1762 ms	3880 KB	Output is correct
73	Correct	1534 ms	3948 KB	Output is correct
74	Correct	1528 ms	4024 KB	Output is correct
75	Correct	1517 ms	3840 KB	Output is correct
76	Correct	1288 ms	3908 KB	Output is correct
77	Correct	1231 ms	3876 KB	Output is correct
78	Correct	1224 ms	3928 KB	Output is correct
79	Correct	1033 ms	3872 KB	Output is correct
80	Correct	1039 ms	3948 KB	Output is correct
81	Correct	1029 ms	4036 KB	Output is correct
82	Correct	978 ms	3736 KB	Output is correct
83	Correct	984 ms	3932 KB	Output is correct
84	Correct	962 ms	3800 KB	Output is correct
85	Correct	2305 ms	9408 KB	Output is correct
86	Correct	222 ms	5100 KB	Output is correct
87	Correct	161 ms	5224 KB	Output is correct
88	Correct	1994 ms	7748 KB	Output is correct
89	Correct	2283 ms	9224 KB	Output is correct
90	Correct	2011 ms	7428 KB	Output is correct
91	Correct	1621 ms	6600 KB	Output is correct
92	Correct	1557 ms	6696 KB	Output is correct
93	Correct	2128 ms	6468 KB	Output is correct
94	Correct	1927 ms	7696 KB	Output is correct
95	Correct	1936 ms	7896 KB	Output is correct
96	Correct	2060 ms	7744 KB	Output is correct
97	Correct	1811 ms	7576 KB	Output is correct
98	Correct	1823 ms	7168 KB	Output is correct
99	Correct	2400 ms	9056 KB	Output is correct
100	Correct	2385 ms	9040 KB	Output is correct
101	Correct	2444 ms	9196 KB	Output is correct
102	Correct	2474 ms	9128 KB	Output is correct
103	Correct	2365 ms	8212 KB	Output is correct
104	Correct	2285 ms	8180 KB	Output is correct
105	Correct	1706 ms	8004 KB	Output is correct
106	Correct	1447 ms	7708 KB	Output is correct
107	Correct	1667 ms	8408 KB	Output is correct
108	Correct	2178 ms	8736 KB	Output is correct
109	Correct	1870 ms	6856 KB	Output is correct