QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104422 | #185. Bridges | fzj2007 | 0 | 50ms | 173976kb | C++14 | 3.7kb | 2023-05-10 17:34:02 | 2023-05-10 17:34:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
namespace IO{
template<typename T>inline bool read(T &x){
x=0;
char ch=getchar();
bool flag=0,ret=0;
while(ch<'0'||ch>'9') flag=flag||(ch=='-'),ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(),ret=1;
x=flag?-x:x;
return ret;
}
template<typename T,typename ...Args>inline bool read(T& a,Args& ...args){
return read(a)&&read(args...);
}
template<typename T>void prt(T x){
if(x>9) prt(x/10);
putchar(x%10+'0');
}
template<typename T>inline void put(T x){
if(x<0) putchar('-'),x=-x;
prt(x);
}
template<typename T>inline void put(char ch,T x){
if(x<0) putchar('-'),x=-x;
prt(x);
putchar(ch);
}
template<typename T,typename ...Args>inline void put(T a,Args ...args){
put(a);
put(args...);
}
template<typename T,typename ...Args>inline void put(const char ch,T a,Args ...args){
put(ch,a);
put(ch,args...);
}
inline void put(string s){
for(int i=0,sz=s.length();i<sz;i++) putchar(s[i]);
}
inline void put(const char* s){
for(int i=0,sz=strlen(s);i<sz;i++) putchar(s[i]);
}
}
using namespace IO;
#define N 200005
#define B 750
int n,m,k,T,q,id[N],b[N];
struct edge{
int u,v,w,l,r;
}e[N<<1];
int s[N],val[N],tim[N],ans[N];
int bel[N],L[N/B+5],R[N/B+5];
vector<int> ins[N],que[N];
struct Opera{
int x,y,val;
Opera(){}
Opera(int _x,int _y,int _val):x(_x),y(_y),val(_val){}
};
struct dsu{
int fa[50005],dep[50005],siz[50005];
vector<Opera> vec;
dsu(){
memset(fa,0,sizeof(fa));
memset(dep,0,sizeof(dep));
memset(siz,0,sizeof(siz));
}
inline void prework(){
for(int i=1;i<=n;i++) fa[i]=i,dep[i]=siz[i]=1;
}
inline int getf(int x){
while(x!=fa[x]) x=fa[x];
return x;
}
inline void merge(int x,int y,int op=0){
x=getf(x),y=getf(y);
if(x==y) return;
if(dep[x]>dep[y]) swap(x,y);
if(op) vec.emplace_back(Opera(x,y,dep[x]==dep[y]));
dep[y]+=dep[x]==dep[y],siz[y]+=siz[x],fa[x]=y;
}
inline void rollback(){
while(vec.size()){
int x=vec.back().x,y=vec.back().y,val=vec.back().val;
fa[x]=x,dep[y]-=val,siz[y]-=siz[x],vec.pop_back();
}
}
}D[N/B+5];
vector<edge> g[N/B+5];
inline void update(int l,int r,int x,int y){
if(bel[l]==bel[r]){
g[bel[l]].emplace_back((edge){x,y,0,l,r});
return;
}
int bl=bel[l]+1,br=bel[r]-1;
for(int i=bl;i<=br;i++) D[i].merge(x,y);
g[bel[l]].emplace_back((edge){x,y,0,l,R[bel[l]]});
g[bel[r]].emplace_back((edge){x,y,0,L[bel[r]],r});
}
inline int query(int p,int x){
int b=bel[p];
for(auto tmp:g[b])
if(tmp.l<=p&&p<=tmp.r) D[b].merge(tmp.u,tmp.v,1);
int res=D[b].siz[D[b].getf(x)];
D[b].rollback();
return res;
}
int main(){
read(n,m),k=m;
for(int i=1;i<=m;i++) read(e[i].u,e[i].v,e[i].w),id[i]=i,e[i].l=1;
read(T);
for(int i=1,a,b,c;i<=T;i++){
read(a,b,c);
if(a==1) e[id[b]].r=i-1,e[++k]=e[id[b]],e[k].w=c,e[k].l=i,id[b]=k;
else q++,s[q]=b,val[q]=c,tim[q]=i;
}
for(int i=1;i<=m;i++) e[id[i]].r=T;
for(int i=1;i<=T;i++){
bel[i]=(i-1)/B+1;
L[bel[i]]=!L[bel[i]]?i:L[bel[i]];
R[bel[i]]=i;
}
for(int i=1;i<=bel[T];i++) D[i].prework();
int num=0;
for(int i=1;i<=k;i++) b[++num]=e[i].w;
for(int i=1;i<=q;i++) b[++num]=val[i];
sort(b+1,b+num+1),num=unique(b+1,b+num+1)-b-1;
for(int i=1;i<=k;i++){
e[i].w=lower_bound(b+1,b+num+1,e[i].w)-b;
ins[e[i].w].emplace_back(i);
}
for(int i=1;i<=q;i++){
val[i]=lower_bound(b+1,b+num+1,val[i])-b;
que[val[i]].emplace_back(i);
}
for(int p=num;p;p--){
for(auto i:ins[p]) update(e[i].l,e[i].r,e[i].u,e[i].v);
for(auto i:que[p]) ans[i]=query(tim[i],s[i]);
}
for(int i=1;i<=q;i++) put('\n',ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 13
Accepted
time: 24ms
memory: 171532kb
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: 16ms
memory: 171704kb
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: 40ms
memory: 171632kb
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: 20ms
memory: 171724kb
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: 40ms
memory: 172496kb
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: 0
Accepted
time: 48ms
memory: 172132kb
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:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 45ms
memory: 172340kb
input:
14 91 14 9 741787656 13 11 380113631 4 1 156765724 5 10 110432834 3 2 1 5 8 39463185 6 7 725978322 13 4 785136504 8 11 446396092 2 1 949863738 10 9 808326751 3 14 623625192 13 1 73346434 4 3 319943247 10 11 874189144 6 5 177923890 14 11 892698206 10 8 602358072 10 12 7684455 14 8 228264999 12 2 8612...
output:
14 14 14 14 1 2 10 14 14 14 1 14 10 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 1 14 14 12 14 1 14 14 14 14 1 14 2 14 14 14 14 14 14 14 14 14 14 13 14 14 14 14 14 14 14 1 14 14 14 2 14 14 14 14 14 14 14 3 14 14 14 14 14 14 14 1 14 14 2 14 14 14 14 14 14 14 14 14 14 14 14 1 14 14 14 14 14 1 14...
result:
ok 5047 lines
Test #8:
score: 0
Accepted
time: 23ms
memory: 173976kb
input:
14 91 14 9 811041661 13 11 347161250 4 1 1000000000 5 10 1000000000 3 2 190616738 5 8 1000000000 6 7 1000000000 13 4 839799889 8 11 1000000000 2 1 1000000000 10 9 925475672 3 14 327778434 13 1 709412306 4 3 696232213 10 11 1000000000 6 5 1000000000 14 11 994412543 10 8 1000000000 10 12 1000000000 14...
output:
10 10 10 10 10 10 14 10 10 14 14 10 10 14 10 14 14 10 10 10 10 10 14 14 13 10 10 10 10 10 14 10 10 10 10 10 10 14 10 10 10 14 10 10 10 10 10 10 10 10 14 10 10 14 10 1 10 13 14 14 14 10 10 10 10 10 10 10 10 10 14 10 10 10 10 14 10 10 10 10 10 10 10 10 10 10 14 10 10 10 10 10 10 14 14 14 10 10 14 14 1...
result:
ok 5085 lines
Test #9:
score: 0
Accepted
time: 35ms
memory: 172160kb
input:
100 100 74 34 685914765 44 9 1 41 36 6 49 22 1 40 84 1 7 40 1 57 31 264482875 16 87 3 66 10 3 68 7 2 92 43 2 33 57 736695588 42 23 2 64 45 1 85 81 4 43 84 1 62 91 2 13 49 2 95 50 1 76 54 1 49 88 1 37 73 2 48 60 1 65 85 3 69 62 2 60 26 1 15 12 1 82 51 2 100 25 3 21 78 1 59 52 1 10 49 2 80 60 2 89 8 3...
output:
84 15 84 84 84 84 84 84 1 84 5 1 84 3 3 1 1 1 1 84 10 84 7 1 84 1 84 1 1 4 84 3 19 1 15 84 84 84 1 84 84 84 84 2 1 84 4 1 2 84 1 84 84 84 2 2 84 84 1 2 84 3 1 5 1 1 4 1 1 84 84 3 20 84 4 6 84 9 4 1 84 1 1 1 84 84 84 84 84 1 84 21 5 2 2 1 1 84 4 84 84 84 5 1 4 6 84 21 1 21 84 84 84 2 84 1 1 1 84 1 84...
result:
ok 4993 lines
Test #10:
score: -13
Wrong Answer
time: 50ms
memory: 172404kb
input:
100 100 74 34 1000000000 44 9 715200993 41 36 904630372 49 22 962500864 40 84 729454076 7 40 377495011 57 31 1000000000 16 87 325040395 66 10 52188391 68 7 212790030 92 43 78499164 33 57 1000000000 42 23 501453286 64 45 269034829 85 81 219465148 43 84 451775169 62 91 579206993 13 49 553447314 95 50 ...
output:
1 60 5 2 24 22 2 1 1 4 40 1 77 72 1 4 1 38 1 2 42 1 3 1 76 1 1 1 2 51 1 28 74 1 38 80 76 1 1 69 3 83 1 5 5 5 83 68 5 2 1 1 1 81 5 2 1 4 1 2 5 52 1 5 78 1 51 2 5 71 2 66 1 84 2 36 1 8 3 1 1 1 78 1 68 81 16 76 2 84 84 2 5 1 63 2 1 63 1 1 74 76 5 1 5 3 1 1 1 1 3 1 1 3 2 5 1 2 24 5 1 1 21 1 1 81 21 4 3 ...
result:
wrong answer 215th lines differ - expected: '12', found: '16'
Subtask #2:
score: 0
Time Limit Exceeded
Test #20:
score: 0
Time Limit Exceeded
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:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #45:
score: 0
Time Limit Exceeded
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:
result:
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%