QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#104419 | #185. Bridges | fzj2007 | 0 | 15ms | 139640kb | C++14 | 3.6kb | 2023-05-10 17:27:28 | 2023-05-10 17:27:29 |
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 350
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[N],siz[N];
vector<Opera> vec;
dsu(){memset(fa,0,sizeof(fa));}
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<=R[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
Runtime Error
Test #1:
score: 13
Accepted
time: 15ms
memory: 139284kb
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: 11ms
memory: 139640kb
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: 12ms
memory: 130676kb
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: 15ms
memory: 134008kb
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: -13
Runtime Error
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:
result:
Subtask #2:
score: 0
Runtime Error
Test #20:
score: 0
Runtime Error
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
Runtime Error
Test #33:
score: 0
Runtime Error
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
Runtime Error
Test #45:
score: 0
Runtime Error
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%