oj.uz

Submission #936423

# Submission time Handle Problem Language Result Execution time Memory
936423 2024-03-01T19:04:42 Z sleepntsheep Bridges (APIO19_bridges) C++17
100 / 100
 2277 ms 5324 KB 
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,tune=native")
#define INLINE inline __attribute__((always_inline))

unsigned X=12345;int rand_(){return(X*=3)/2;}
int(*compar)(int,int);
void sort(int*aa,int l,int r)
{
    while(l<r)
    {
        int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)];
        while(j<k)switch(compar(aa[j],p)){case 0:++j;break;case -1:t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;break;case 1:t=aa[--k],aa[k]=aa[j],aa[j]=t;break;}
        sort(aa,l,i),l=k;
    }
}

#define N 50005
#define S 600
int n,m,e[100000][3],h[N],q,b[100000][3],delta[100000],stat[100000],rm,rizz[9000],sm,ask[9000],am;

int savemode=1,p[N],sve[9000][3],svtop;
int df(int x){return p[x]<0?x:df(p[x]);}

INLINE void dun(int u,int v){
    if((u=df(u))==(v=df(v)))return;
    if(-p[u]<-p[v]){int t=u;u=v;v=t;}
    if(savemode)sve[svtop][0]=u,sve[svtop][1]=v,sve[svtop][2]=p[v],++svtop;
    p[u]+=p[v],p[v]=u;
}

INLINE void drb(){int k=--svtop,u=sve[k][0],v=sve[k][1],pv=sve[k][2];p[u]-=(p[v]=pv);}

int compar_edge_dec(int i,int j){return e[i][2]>e[j][2]?-1:e[i][2]<e[j][2]?1:0;}
int compar_ask_dec(int i,int j){return b[i][2]<b[j][2]?1:b[i][2]>b[j][2]?-1:0;}
int compar_edge_dec2(int i,int j){return e[i][2]>e[j][2];}
int compar_ask_dec2(int i,int j){return b[i][2]>b[j][2];}

#include<algorithm>
int onrizz[100000],ans[100000];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)scanf("%d%d%d",e[i],e[i]+1,e[i]+2);
    scanf("%d",&q);
    for(int i=0;i<q;++i){scanf("%d%d%d",b[i],b[i]+1,b[i]+2);if(b[i][0]==1)--b[i][1];}
    for(int l=0;l*S<q;++l)
    {
        memset(p,-1,sizeof p);svtop=0;
        for(int j=l*S;j<l*S+S&&j<q;++j)if(b[j][0]==1)++delta[b[j][1]];else ask[am++]=j;
        for(int j=0;j<m;++j)if(!delta[j])stat[sm++]=j;else rizz[rm++]=j;
        std::sort(stat,stat+sm,compar_edge_dec2); std::sort(ask,ask+am,compar_ask_dec2);
        int ep=0;
        for(int ii=0;ii<am;++ii)
        {
            int w=b[ask[ii]][2];
            savemode=0;while(ep<sm&&e[stat[ep]][2]>=w)dun(e[stat[ep]][0],e[stat[ep]][1]),++ep;savemode=1;
            int eee=svtop;
            for(int j=ask[ii]-1;j>=l*S;--j)
            {
                if(b[j][0]==1&&!onrizz[b[j][1]])
                {
                    if(b[j][2]>=w)dun(e[b[j][1]][0],e[b[j][1]][1]);
                    onrizz[b[j][1]]=1;
                }
            }
            for(int jj=0;jj<rm;++jj)if(!onrizz[rizz[jj]]&&e[rizz[jj]][2]>=w)
                dun(e[rizz[jj]][0],e[rizz[jj]][1]);
            ans[ask[ii]]=-p[df(b[ask[ii]][1])];
            while(svtop>eee)drb();
            for(int j=ask[ii]-1;j>=l*S;--j) onrizz[b[j][1]]=0;
        }
        sm=rm=am=0;
        for(int j=l*S;j<l*S+S&&j<q;++j)if(b[j][0]==1)--delta[b[j][1]],e[b[j][1]][2]=b[j][2];
    }
    for(int i=0;i<q;++i)if(b[i][0]==2)printf("%d\n",ans[i]);
}

Compilation message

bridges.cpp: In function 'int main()':
bridges.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |     scanf("%d%d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~
bridges.cpp:47:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     for(int i=0;i<m;++i)scanf("%d%d%d",e[i],e[i]+1,e[i]+2);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bridges.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
bridges.cpp:49:31: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     for(int i=0;i<q;++i){scanf("%d%d%d",b[i],b[i]+1,b[i]+2);if(b[i][0]==1)--b[i][1];}
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 16 ms 2716 KB Output is correct
4 Correct 7 ms 2648 KB Output is correct
5 Correct 16 ms 2648 KB Output is correct
6 Correct 12 ms 2652 KB Output is correct
7 Correct 12 ms 2648 KB Output is correct
8 Correct 13 ms 2656 KB Output is correct
9 Correct 11 ms 2652 KB Output is correct
10 Correct 13 ms 2652 KB Output is correct
11 Correct 12 ms 2648 KB Output is correct
12 Correct 13 ms 2660 KB Output is correct
13 Correct 20 ms 2652 KB Output is correct
14 Correct 15 ms 2652 KB Output is correct
15 Correct 14 ms 2652 KB Output is correct
16 Correct 15 ms 2648 KB Output is correct
17 Correct 12 ms 2708 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 3988 KB Output is correct
2 Correct 1112 ms 3952 KB Output is correct
3 Correct 1087 ms 4132 KB Output is correct
4 Correct 1079 ms 3776 KB Output is correct
5 Correct 1069 ms 4056 KB Output is correct
6 Correct 1219 ms 4304 KB Output is correct
7 Correct 1275 ms 4064 KB Output is correct
8 Correct 1178 ms 4196 KB Output is correct
9 Correct 61 ms 3156 KB Output is correct
10 Correct 491 ms 4056 KB Output is correct
11 Correct 498 ms 3920 KB Output is correct
12 Correct 978 ms 4088 KB Output is correct
13 Correct 1002 ms 3932 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 716 ms 4276 KB Output is correct
2 Correct 312 ms 3336 KB Output is correct
3 Correct 746 ms 3920 KB Output is correct
4 Correct 734 ms 3588 KB Output is correct
5 Correct 59 ms 3160 KB Output is correct
6 Correct 717 ms 3540 KB Output is correct
7 Correct 684 ms 3748 KB Output is correct
8 Correct 667 ms 3452 KB Output is correct
9 Correct 603 ms 3664 KB Output is correct
10 Correct 605 ms 3668 KB Output is correct
11 Correct 639 ms 3560 KB Output is correct
12 Correct 585 ms 3720 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2060 ms 4740 KB Output is correct
2 Correct 58 ms 3232 KB Output is correct
3 Correct 207 ms 3740 KB Output is correct
4 Correct 82 ms 3876 KB Output is correct
5 Correct 903 ms 5324 KB Output is correct
6 Correct 1949 ms 4648 KB Output is correct
7 Correct 886 ms 4792 KB Output is correct
8 Correct 882 ms 4180 KB Output is correct
9 Correct 894 ms 4292 KB Output is correct
10 Correct 931 ms 4180 KB Output is correct
11 Correct 1435 ms 4380 KB Output is correct
12 Correct 1400 ms 4216 KB Output is correct
13 Correct 1473 ms 4800 KB Output is correct
14 Correct 790 ms 5200 KB Output is correct
15 Correct 831 ms 4856 KB Output is correct
16 Correct 1986 ms 4912 KB Output is correct
17 Correct 2005 ms 4676 KB Output is correct
18 Correct 1972 ms 4848 KB Output is correct
19 Correct 2005 ms 4968 KB Output is correct
20 Correct 1665 ms 4964 KB Output is correct
21 Correct 1636 ms 4648 KB Output is correct
22 Correct 1911 ms 4772 KB Output is correct
23 Correct 1032 ms 4708 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1035 ms 3988 KB Output is correct
2 Correct 1112 ms 3952 KB Output is correct
3 Correct 1087 ms 4132 KB Output is correct
4 Correct 1079 ms 3776 KB Output is correct
5 Correct 1069 ms 4056 KB Output is correct
6 Correct 1219 ms 4304 KB Output is correct
7 Correct 1275 ms 4064 KB Output is correct
8 Correct 1178 ms 4196 KB Output is correct
9 Correct 61 ms 3156 KB Output is correct
10 Correct 491 ms 4056 KB Output is correct
11 Correct 498 ms 3920 KB Output is correct
12 Correct 978 ms 4088 KB Output is correct
13 Correct 1002 ms 3932 KB Output is correct
14 Correct 716 ms 4276 KB Output is correct
15 Correct 312 ms 3336 KB Output is correct
16 Correct 746 ms 3920 KB Output is correct
17 Correct 734 ms 3588 KB Output is correct
18 Correct 59 ms 3160 KB Output is correct
19 Correct 717 ms 3540 KB Output is correct
20 Correct 684 ms 3748 KB Output is correct
21 Correct 667 ms 3452 KB Output is correct
22 Correct 603 ms 3664 KB Output is correct
23 Correct 605 ms 3668 KB Output is correct
24 Correct 639 ms 3560 KB Output is correct
25 Correct 585 ms 3720 KB Output is correct
26 Correct 1031 ms 3840 KB Output is correct
27 Correct 1119 ms 4048 KB Output is correct
28 Correct 1084 ms 3944 KB Output is correct
29 Correct 989 ms 3904 KB Output is correct
30 Correct 1120 ms 3788 KB Output is correct
31 Correct 1121 ms 4088 KB Output is correct
32 Correct 1124 ms 3816 KB Output is correct
33 Correct 1084 ms 3972 KB Output is correct
34 Correct 1096 ms 3828 KB Output is correct
35 Correct 1070 ms 3844 KB Output is correct
36 Correct 1018 ms 4068 KB Output is correct
37 Correct 995 ms 4040 KB Output is correct
38 Correct 999 ms 3864 KB Output is correct
39 Correct 1075 ms 3968 KB Output is correct
40 Correct 933 ms 3988 KB Output is correct
41 Correct 947 ms 3928 KB Output is correct
42 Correct 866 ms 3820 KB Output is correct
43 Correct 905 ms 3740 KB Output is correct
44 Correct 865 ms 3804 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 16 ms 2716 KB Output is correct
4 Correct 7 ms 2648 KB Output is correct
5 Correct 16 ms 2648 KB Output is correct
6 Correct 12 ms 2652 KB Output is correct
7 Correct 12 ms 2648 KB Output is correct
8 Correct 13 ms 2656 KB Output is correct
9 Correct 11 ms 2652 KB Output is correct
10 Correct 13 ms 2652 KB Output is correct
11 Correct 12 ms 2648 KB Output is correct
12 Correct 13 ms 2660 KB Output is correct
13 Correct 20 ms 2652 KB Output is correct
14 Correct 15 ms 2652 KB Output is correct
15 Correct 14 ms 2652 KB Output is correct
16 Correct 15 ms 2648 KB Output is correct
17 Correct 12 ms 2708 KB Output is correct
18 Correct 1035 ms 3988 KB Output is correct
19 Correct 1112 ms 3952 KB Output is correct
20 Correct 1087 ms 4132 KB Output is correct
21 Correct 1079 ms 3776 KB Output is correct
22 Correct 1069 ms 4056 KB Output is correct
23 Correct 1219 ms 4304 KB Output is correct
24 Correct 1275 ms 4064 KB Output is correct
25 Correct 1178 ms 4196 KB Output is correct
26 Correct 61 ms 3156 KB Output is correct
27 Correct 491 ms 4056 KB Output is correct
28 Correct 498 ms 3920 KB Output is correct
29 Correct 978 ms 4088 KB Output is correct
30 Correct 1002 ms 3932 KB Output is correct
31 Correct 716 ms 4276 KB Output is correct
32 Correct 312 ms 3336 KB Output is correct
33 Correct 746 ms 3920 KB Output is correct
34 Correct 734 ms 3588 KB Output is correct
35 Correct 59 ms 3160 KB Output is correct
36 Correct 717 ms 3540 KB Output is correct
37 Correct 684 ms 3748 KB Output is correct
38 Correct 667 ms 3452 KB Output is correct
39 Correct 603 ms 3664 KB Output is correct
40 Correct 605 ms 3668 KB Output is correct
41 Correct 639 ms 3560 KB Output is correct
42 Correct 585 ms 3720 KB Output is correct
43 Correct 2060 ms 4740 KB Output is correct
44 Correct 58 ms 3232 KB Output is correct
45 Correct 207 ms 3740 KB Output is correct
46 Correct 82 ms 3876 KB Output is correct
47 Correct 903 ms 5324 KB Output is correct
48 Correct 1949 ms 4648 KB Output is correct
49 Correct 886 ms 4792 KB Output is correct
50 Correct 882 ms 4180 KB Output is correct
51 Correct 894 ms 4292 KB Output is correct
52 Correct 931 ms 4180 KB Output is correct
53 Correct 1435 ms 4380 KB Output is correct
54 Correct 1400 ms 4216 KB Output is correct
55 Correct 1473 ms 4800 KB Output is correct
56 Correct 790 ms 5200 KB Output is correct
57 Correct 831 ms 4856 KB Output is correct
58 Correct 1986 ms 4912 KB Output is correct
59 Correct 2005 ms 4676 KB Output is correct
60 Correct 1972 ms 4848 KB Output is correct
61 Correct 2005 ms 4968 KB Output is correct
62 Correct 1665 ms 4964 KB Output is correct
63 Correct 1636 ms 4648 KB Output is correct
64 Correct 1911 ms 4772 KB Output is correct
65 Correct 1032 ms 4708 KB Output is correct
66 Correct 1031 ms 3840 KB Output is correct
67 Correct 1119 ms 4048 KB Output is correct
68 Correct 1084 ms 3944 KB Output is correct
69 Correct 989 ms 3904 KB Output is correct
70 Correct 1120 ms 3788 KB Output is correct
71 Correct 1121 ms 4088 KB Output is correct
72 Correct 1124 ms 3816 KB Output is correct
73 Correct 1084 ms 3972 KB Output is correct
74 Correct 1096 ms 3828 KB Output is correct
75 Correct 1070 ms 3844 KB Output is correct
76 Correct 1018 ms 4068 KB Output is correct
77 Correct 995 ms 4040 KB Output is correct
78 Correct 999 ms 3864 KB Output is correct
79 Correct 1075 ms 3968 KB Output is correct
80 Correct 933 ms 3988 KB Output is correct
81 Correct 947 ms 3928 KB Output is correct
82 Correct 866 ms 3820 KB Output is correct
83 Correct 905 ms 3740 KB Output is correct
84 Correct 865 ms 3804 KB Output is correct
85 Correct 2257 ms 4800 KB Output is correct
86 Correct 223 ms 4208 KB Output is correct
87 Correct 117 ms 4180 KB Output is correct
88 Correct 1059 ms 5076 KB Output is correct
89 Correct 2208 ms 4908 KB Output is correct
90 Correct 1084 ms 4512 KB Output is correct
91 Correct 1103 ms 4304 KB Output is correct
92 Correct 1086 ms 3880 KB Output is correct
93 Correct 1253 ms 4088 KB Output is correct
94 Correct 1716 ms 4364 KB Output is correct
95 Correct 1698 ms 4180 KB Output is correct
96 Correct 1696 ms 4348 KB Output is correct
97 Correct 1002 ms 4812 KB Output is correct
98 Correct 969 ms 4864 KB Output is correct
99 Correct 2223 ms 4752 KB Output is correct
100 Correct 2254 ms 4820 KB Output is correct
101 Correct 2277 ms 4896 KB Output is correct
102 Correct 2229 ms 4804 KB Output is correct
103 Correct 1908 ms 4552 KB Output is correct
104 Correct 1885 ms 4492 KB Output is correct
105 Correct 1791 ms 4440 KB Output is correct
106 Correct 1613 ms 4372 KB Output is correct
107 Correct 1753 ms 4948 KB Output is correct
108 Correct 2127 ms 4852 KB Output is correct
109 Correct 1206 ms 4416 KB Output is correct