QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#100172 | #185. Bridges | Bronya | 0 | 1976ms | 14952kb | C++20 | 2.7kb | 2023-04-24 20:57:45 | 2023-04-24 20:57:49 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,Q;
struct edge{
int u,v;
int a,b;
}e[200005];
int id[200005];
int ans[200005];
bool cmpp(int x,int y){
return (e[x].b<e[y].b);
}
struct bcj{
int siz;
int len;
}val[200005];
int fa[200005];
stack<pair<int,bcj>>rc;
int Find(int u){
return (fa[u]!=u?Find(fa[u]):u);
}
inline void merge(int u,int v){
u=Find(u),v=Find(v);
if(val[u].len<val[v].len)swap(u,v);
if(u!=v){
fa[v]=u;
rc.push(make_pair(v,val[u]));
}
else rc.push(make_pair(u,val[u]));
if(u!=v)val[u].siz+=val[v].siz,val[u].len=max(val[v].len+1,val[u].len);
}
inline void del(int u){
while(rc.size()>u){
int v=rc.top().first;
val[fa[v]]=rc.top().second;
fa[v]=v;
rc.pop();
}
}
set<pair<int,int> >hav;
vector<int>A;
vector<int>B;
int main(){
// freopen("1.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].b);e[i].b=-e[i].b;
id[i]=i;
}
scanf("%d",&Q);
for(int i=1;i<=m;i++)e[i].a=m+Q+1;
for(int i=1;i<=Q;i++){
int opt;
scanf("%d",&opt);
if(opt==1){
int u;
scanf("%d",&u);
e[i+m]=e[id[u]];
e[id[u]].a=i+m-1;
scanf("%d",&e[i+m].b);e[i+m].b=-e[i+m].b;
id[u]=i+m;
}
else scanf("%d%d",&e[i+m].u,&e[i+m].b),e[i+m].a=-1,e[i+m].b=-e[i+m].b;
}
// for(int i=1;i<=m+Q;i++)cout<<e[i].a<<endl;
for(int i=1;i<=n;i++)fa[i]=i,val[i].siz=1;
int siz=sqrt(m*__lg(m));
for(int i=1;(i-1)*siz+1<=m+Q;i++){
A.clear();B.clear();
for(auto j=hav.begin();j!=hav.end();j++){
int u=j->second;
if(e[u].a<=min(i*siz,m+Q))A.push_back(u);
}
for(int j=0;j<A.size();j++)hav.erase(hav.lower_bound(make_pair(e[A[j]].b,A[j])));
for(int j=(i-1)*siz+1;j<=min(i*siz,m+Q);j++){
if(e[j].a==-1)B.push_back(j);
else A.push_back(j);
}
sort(B.begin(),B.end(),cmpp);
int L=0;
// cout<<L<<" "<<B.size()<<endl;
for(auto j=hav.begin();j!=hav.end();j++){
while(L<B.size()&&e[B[L]].b<j->first){
int now=rc.size();
for(int k=0;k<A.size();k++)
if(A[k]<=B[L]&&e[A[k]].a>=B[L]&&e[A[k]].b<=e[B[L]].b)
merge(e[A[k]].u,e[A[k]].v);
int f1=Find(e[B[L]].u);
ans[B[L]]=val[f1].siz;
del(now);
L++;
}
merge(e[j->second].u,e[j->second].v);
}
while(L<B.size()){
int now=rc.size();
for(int k=0;k<A.size();k++)
if(A[k]<=B[L]&&e[A[k]].a>=B[L]&&e[A[k]].b<=e[B[L]].b)
merge(e[A[k]].u,e[A[k]].v);
int f1=Find(e[B[L]].u);
ans[B[L]]=val[f1].siz;
del(now);
L++;
}
del(0);
for(int j=0;j<A.size();j++){
if(e[A[j]].a<=i*siz)continue;
else hav.insert(make_pair(e[A[j]].b,A[j]));
}
}
for(int i=1;i<=m+Q;i++)
if(e[i].a==-1)printf("%d\n",ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 13
Accepted
time: 2ms
memory: 3648kb
input:
3 4 1 2 5 2 3 2 3 1 4 2 3 8 5 2 1 5 1 4 1 2 2 5 1 1 1 2 3 2
output:
3 2 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 3688kb
input:
7 8 1 2 5 1 6 5 2 3 5 2 7 5 3 4 5 4 5 5 5 6 5 6 7 5 12 2 1 6 1 1 1 2 1 2 1 2 3 2 2 2 1 5 2 1 3 1 2 2 4 2 4 2 1 8 1 2 1 1 2 1 3
output:
1 7 7 5 7 7 4
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 3712kb
input:
5 5 5 3 81 2 4 49 4 1 63 4 3 74 1 2 85 10 2 2 22 2 2 20 1 3 49 2 1 77 1 3 44 1 1 6 2 3 49 2 4 31 2 2 54 2 2 7
output:
5 5 2 4 4 2 4
result:
ok 7 lines
Test #4:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
5 10 1 3 51 1 2 74 2 4 63 1 4 86 2 5 9 5 1 28 5 4 1 2 1 23 2 5 16 3 1 75 10 2 2 37 1 6 24 1 1 24 2 5 65 1 7 57 2 1 82 2 1 26 1 4 12 2 2 15 1 4 70
output:
4 1 2 5 5
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 17ms
memory: 3924kb
input:
100 1000 26 42 977322268 4 29 374382133 1 19 717262653 80 56 835233390 58 54 591443635 63 6 579687470 85 81 118110131 33 100 533388119 24 46 591205239 94 32 637495476 60 93 638216409 55 7 413175730 38 43 414269997 48 30 773236579 67 27 441100383 44 36 784705206 28 56 300064078 13 60 490548719 94 19 ...
output:
100 100 100 100 100 100 100 100 17 100 100 100 100 100 5 100 98 100 100 100 100 100 100 100 100 100 100 100 100 96 100 2 42 100 100 100 86 97 100 100 100 98 100 100 100 100 100 97 100 100 100 100 100 100 100 100 100 100 100 100 100 98 100 100 100 100 100 5 100 100 100 100 100 98 100 100 100 100 1 10...
result:
ok 4938 lines
Test #6:
score: -13
Time Limit Exceeded
input:
1 0 10000 2 1 198824732 2 1 485321921 2 1 632483476 2 1 51814372 2 1 599796663 2 1 786502474 2 1 231528808 2 1 911511073 2 1 372581312 2 1 168699670 2 1 155928174 2 1 636544973 2 1 221309003 2 1 934838177 2 1 927074369 2 1 66460573 2 1 854380894 2 1 763039163 2 1 203254324 2 1 525763932 2 1 58538356...
output:
result:
Subtask #2:
score: 0
Time Limit Exceeded
Test #20:
score: 16
Accepted
time: 1285ms
memory: 11212kb
input:
50000 49999 1 2 976392398 2 3 773336157 3 4 849545817 4 5 194340376 5 6 386778507 6 7 40561907 7 8 260116638 8 9 85673124 9 10 149683208 10 11 724746156 11 12 155084527 12 13 416939763 13 14 753621724 14 15 384948880 15 16 625917615 16 17 833747431 17 18 764302034 18 19 4518648 19 20 405679793 20 21...
output:
7 2 24 1 3 8 1 2 6 2 535 4 3 2 7 13 40 110 3 41 6 1 108 491 28 1 1 4 2 11 5 9 2 1 2 1 9 1 1 3 1 14 3 1 1 10 44 3 2 3 3 1 1 18 3 2 2 2 1 9 1 15 17 7 1 1 1 4 1 2 6 3 1 1 5 1 10 1 5 2 1 14 14 3 28 17 1 6 1 3 1 9 3 10 2 32 54 4 1 2 2 18 1 1 5 1 11 2 10 1 2 5 4 1 1 2 3 4 1 1 128 17 3 1 2 2 1 160 1 1 2 3 ...
result:
ok 49863 lines
Test #21:
score: 0
Accepted
time: 1294ms
memory: 10232kb
input:
50000 49999 1 2 491 2 3 15360 3 4 24312 4 5 17754 5 6 40601 6 7 30620 7 8 69533 8 9 144923 9 10 304551 10 11 264913 11 12 265173 12 13 135700 13 14 61571 14 15 6841 15 16 413217 16 17 596083 17 18 157633 18 19 68400 19 20 348725 20 21 494086 21 22 327898 22 23 569190 23 24 195301 24 25 402492 25 26 ...
output:
6 7 16 2 13 24 24 8 1 3 5 257 1 3 6 1 112 2 5 2 11 1 6 2 6 1 1 4 177 7 19 1 1 42 10 2 25 4 24 4 1 3 3 2 1 1 5 1 3 2 13 1 1 1 2 3 5 3 9 2 16 4 10 6 7 3 1 2 17 37 3 1 4 1 4 1 3 7 1 2 2 1 135 3 34 5 2 2 8 2 1 1 1 1 4 3 1 3 2 5 2 1 5 1 2 5 503 3 1 9 7 1 2 4 2 3 5 9 2 15 3 7 9 16 1 28 5 2 5 4 2 3 8 9 4 1...
result:
ok 49979 lines
Test #22:
score: 0
Accepted
time: 1240ms
memory: 10164kb
input:
50000 49999 1 2 20928 2 3 33937 3 4 35582 4 5 123172 5 6 100214 6 7 105156 7 8 46684 8 9 124995 9 10 13728 10 11 209960 11 12 206098 12 13 146953 13 14 370445 14 15 141005 15 16 536276 16 17 80350 17 18 258276 18 19 401626 19 20 32874 20 21 125207 21 22 357075 22 23 598244 23 24 46414 24 25 609917 2...
output:
3 1 1 1 2 1 2 10 7 1 43 3 6 1 4 1 8 1 82 5 3 1 1 2 1 11 5 45 21 1 1 10 2 5 8 2 1 12 1 29 2 1 4 5 2 56 3 3 3 14 1 1 29 9 160 4 3 5 2 2 1 2 6 3 2 11 2 8 1 8 3 3 9 199 1 1 1 1 1 1 1 11 23 2 2 9 339 2 2 1 2 3 1 1 116 6 5 5 10 3 1 1 2 1 18 1 1 6 1 1 8 3 3 1 1 24 1 1 3 1 1 5 12 10 1 6 1 3 2 4 1 2 1 5 6 1 ...
result:
ok 50005 lines
Test #23:
score: 0
Accepted
time: 1342ms
memory: 10168kb
input:
50000 49999 1 2 111167988 2 3 402479521 3 4 873342766 4 5 303335487 5 6 357259867 6 7 944570848 7 8 227864068 8 9 137899415 9 10 782881158 10 11 545137901 11 12 125756079 12 13 713912399 13 14 516355545 14 15 306731193 15 16 244028251 16 17 175980262 17 18 956260270 18 19 92690286 19 20 344996907 20...
output:
1 8 1 1 1 1 6 11 21 12 5 3 105 1 1 2 4 5 1 16 1 2 1 3 1 3 2 1 1 2 1 30 2 29 9 8 6 16 1 24 5 8 2 1 5 33 10 12 5 28 10 2 1 1 6 1 2 1 1 1 1 17 7 12 2 3 10 6 2 89 38 2 2 1 2 5 6 1 1 107 47 1 1 1 1 9 1 1 13 2 12 6 1 1 9 9 2 16 1 2 2 2 15 1 4 5 5 1 1 116 5 1 7 5 3 18 1 1 1 14 1 2 1 1 1 3185 1 3 3 2 1 3 7 ...
result:
ok 49979 lines
Test #24:
score: 0
Accepted
time: 1388ms
memory: 10136kb
input:
50000 49999 1 2 993457878 2 3 126364173 3 4 200415238 4 5 739704607 5 6 676532686 6 7 557507714 7 8 71727068 8 9 337809709 9 10 681106495 10 11 599345798 11 12 346312387 12 13 39200895 13 14 943426213 14 15 506779546 15 16 379338416 16 17 14615880 17 18 816406736 18 19 211045210 19 20 838922528 20 2...
output:
5 9 18 53 19 1 25 4 19 1 1 1 1 1 11 1 1 2 1 9 1 13 16 5 1 2 1 1 1 7 1 1 16 1 1 5 3 2 3 3 11 2 1 1 12 1 16987 4 12 1 1 1 5 5 5 1 1 4 1 4 2 1 3 1 4 1 1 2 5 2 18 1 3 200 1 4 2 7 1 1 1 2 44 2 1 10 11 2 3 12 1 3 4 10 4 7 1 16 6 1 13 4 1 5 3 2 1 2 2 2 1 31 40 3 2 1 3 1 86 2 2 1 1 1 1 15 2 1 1 1 6 1 1 7 1 ...
result:
ok 50005 lines
Test #25:
score: 0
Accepted
time: 1976ms
memory: 10056kb
input:
50000 49999 1 2 2180 2 3 39922 3 4 2857 4 5 41405 5 6 71574 6 7 34628 7 8 271216 8 9 134571 9 10 77206 10 11 98084 11 12 86039 12 13 449514 13 14 490107 14 15 450572 15 16 139688 16 17 639236 17 18 247981 18 19 75121 19 20 300881 20 21 7682 21 22 248842 22 23 599408 23 24 647942 24 25 7276 25 26 470...
output:
49496 49499 49314 30098 32346 32346 49499 30098 42345 4779 49496 42345 49314 32346 49496 49314 30098 1640 30098 30098 30098 6969 6968 40954 49314 30098 2248 30098 30098 403 40954 6969 49314 6969 30098 49498 30098 4779 40954 49499 6968 42345 30098 32346 1345 32346 49314 32346 40954 32346 6969 6969 33...
result:
ok 49911 lines
Test #26:
score: 0
Accepted
time: 1877ms
memory: 10360kb
input:
49999 49998 1 2 2541 2 3 57948 3 4 37666 4 5 66268 5 6 42284 6 7 115405 7 8 248366 8 9 262167 9 10 145846 10 11 47627 11 12 431021 12 13 218051 13 14 401077 14 15 549059 15 16 169347 16 17 363982 17 18 490171 18 19 370535 19 20 480055 20 21 327730 21 22 278018 22 23 231965 23 24 256156 24 25 329573 ...
output:
450 33828 47494 47494 1249 47493 9064 9064 24764 8175 47493 8175 33828 19203 19203 3968 1811 8175 5561 1689 42003 8175 33828 42003 33828 47494 19203 5561 24764 47494 3968 16782 24764 19203 24764 47494 24764 8175 24764 47493 9064 75 9064 1689 47494 1689 1689 24764 5561 2976 33828 3968 33828 78 24764 ...
result:
ok 50105 lines
Test #27:
score: 0
Accepted
time: 1818ms
memory: 10132kb
input:
49999 49998 1 2 23701 2 3 57539 3 4 70283 4 5 136271 5 6 141212 6 7 184696 7 8 228429 8 9 29895 9 10 31218 10 11 282781 11 12 29995 12 13 131524 13 14 133988 14 15 197273 15 16 351724 16 17 391575 17 18 253620 18 19 611546 19 20 216997 20 21 305541 21 22 118275 22 23 306021 23 24 482979 24 25 709132...
output:
26373 8528 1944 10472 1430 6356 3806 5934 1944 49998 8528 11437 369 363 36932 4327 3351 3351 3806 6496 1944 49973 5934 13041 19188 1857 652 2143 13254 13254 12975 49998 599 8528 1944 10472 5934 8528 19 10472 13254 10472 1935 4327 6356 11339 36932 13254 10472 4257 3806 610 6496 5934 2220 11437 1300 4...
result:
ok 50026 lines
Test #28:
score: -16
Time Limit Exceeded
input:
1 0 100000 2 1 710454586 2 1 30174257 2 1 685675008 2 1 417816804 2 1 327755609 2 1 841371333 2 1 301370841 2 1 143821498 2 1 232099091 2 1 977178764 2 1 572665966 2 1 913418066 2 1 808399404 2 1 22331931 2 1 434460344 2 1 40437984 2 1 997406768 2 1 40071081 2 1 268638772 2 1 541398526 2 1 983507437...
output:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #33:
score: 17
Accepted
time: 876ms
memory: 9952kb
input:
32767 32766 1 2 152523690 1 3 736211233 2 4 163158345 2 5 200010458 3 6 902682843 3 7 427399287 4 8 770411775 4 9 322256303 5 10 252775416 5 11 346597970 6 12 297314023 6 13 727299741 7 14 985621564 7 15 101953231 8 16 405434218 8 17 421655547 9 18 817411034 9 19 310455840 10 20 355126049 10 21 7038...
output:
1 1 2 2 6 6 12547 1 1 1793 3 41 1 37 29734 8197 1 1 1 2 11 3 7 5 18 39 13 136 1 2 1 1 4 2 177 3 279 2 36 114 53 4 9 3 2 1 21 6 2 2 5 2 1 6 7 1 5 4 11 23129 288 196 8 1 5 9 3 1 4 45 4 1 1 5 3 3 10 18 91 1 16 829 24 1 2 8 1247 10 2 1 7 20323 8 1 2 28551 1 6 1 12 4 3 1 27 1 1 1 1 2 3 1 7 1 487 1 21 15 ...
result:
ok 50019 lines
Test #34:
score: 0
Accepted
time: 352ms
memory: 8412kb
input:
8191 8190 1 2 217141764 1 3 529497259 2 4 779147272 2 5 691696039 3 6 48118037 3 7 603814603 4 8 696908741 4 9 217271102 5 10 68704258 5 11 22697519 6 12 683544026 6 13 723792342 7 14 793130995 7 15 92576446 8 16 327755609 8 17 103625834 9 18 543827967 9 19 341371333 10 20 640187172 10 21 85328878 1...
output:
3231 8191 580 3382 8191 8191 8191 8191 3212 6 4 7 6 3187 6120 6152 4 457 8191 7 2 8191 8191 8191 8191 8191 4 8191 8191 8191 8191 3605 8191 7 8191 5715 6975 8191 8191 4289 2 8191 6977 8191 2 8191 8191 4 1 1 8191 1 8191 8191 11 8191 8191 222 1 8191 5905 8191 8191 8060 8191 8191 8191 2 1 8191 8191 8191...
result:
ok 49969 lines
Test #35:
score: 0
Accepted
time: 913ms
memory: 10032kb
input:
32767 32766 1 2 217141764 1 3 529497259 2 4 762168910 2 5 862501617 3 6 287569355 3 7 60434037 4 8 741381891 4 9 846044727 5 10 559556243 5 11 841922729 6 12 260807264 6 13 108798675 7 14 165384865 7 15 803171234 8 16 680929744 8 17 534495504 9 18 618761142 9 19 633256718 10 20 244069182 10 21 40934...
output:
32767 32767 32767 32767 32767 32767 32767 32767 32767 32767 3 32767 16965 32767 2 26 32767 32767 6 1 32767 7826 32767 1 21971 7 32767 12668 5289 162 32767 15263 32767 11 32767 3 4 32767 18 118 32767 1 32767 32767 32767 5 32767 32767 39 32767 267 32767 32767 32767 32767 32767 1 7 32767 2 32767 1 228 ...
result:
ok 50058 lines
Test #36:
score: 0
Accepted
time: 857ms
memory: 9012kb
input:
32767 32766 1 2 960028533 1 3 932018255 2 4 966739858 2 5 978817181 3 6 951511415 3 7 993940257 4 8 988418327 4 9 995978961 5 10 810804356 5 11 990996089 6 12 988830283 6 13 964972868 7 14 860937540 7 15 840655680 8 16 840257957 8 17 761892560 9 18 901480224 9 19 889396012 10 20 884899819 10 21 9367...
output:
5 1 6 19293 1 17937 1 1 1 1 1 3 7 1 4 6883 32026 1 1 1 2 5824 2 19 2 28839 7 1 8 12099 19229 27469 2 3 1 10692 1 21275 1 2 1 31 1 1 1 15551 1 1 1 32498 7 31105 29865 1870 31927 1 3 1 1 1 1 27524 1 9 29426 4 1 12 4 26271 1 18126 2 1 1 1 1 31028 6 8 14285 1 3103 3 2 8 2 31181 1 1 1 21314 1 7 2 1 1 244...
result:
ok 50058 lines
Test #37:
score: -17
Time Limit Exceeded
input:
1 0 100000 2 1 710454586 2 1 30174257 2 1 685675008 2 1 417816804 2 1 327755609 2 1 841371333 2 1 301370841 2 1 143821498 2 1 232099091 2 1 977178764 2 1 572665966 2 1 913418066 2 1 808399404 2 1 22331931 2 1 434460344 2 1 40437984 2 1 997406768 2 1 40071081 2 1 268638772 2 1 541398526 2 1 983507437...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #45:
score: 14
Accepted
time: 1494ms
memory: 14952kb
input:
50000 100000 35231 1616 822934828 1668 2202 768458723 26049 41810 238904165 15936 42751 466996423 41068 21425 588205829 29502 11760 732391267 13029 44741 930695124 46168 22085 155239713 9505 43779 638894800 18665 43842 298794735 41763 15511 727702105 7865 27776 53447691 32904 34081 844499614 26327 9...
output:
2 2 1 48165 37106 1 48830 1 47126 3 37777 1 14 1 1 24 1 48755 44817 17617 24322 48909 7 47708 1 41147 48949 45939 48022 1 26304 1 1 22363 24527 46076 37978 1 1 2 44508 1 47625 48554 1 2 4 48711 48431 41315 2 2 9364 3 37323 46978 39881 32373 5 39140 47126 44635 47960 1 48141 47192 28 27190 38467 4 48...
result:
ok 100000 lines
Test #46:
score: -14
Time Limit Exceeded
input:
1 0 100000 2 1 449565301 2 1 418018081 2 1 566914037 2 1 386096903 2 1 325815043 2 1 515513392 2 1 349622300 2 1 5042450 2 1 469351640 2 1 219472495 2 1 510850771 2 1 885705436 2 1 594457820 2 1 410756749 2 1 959667810 2 1 479458147 2 1 705147675 2 1 140732217 2 1 281668854 2 1 333164650 2 1 3934393...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%