QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104419#185. Bridgesfzj20070 15ms139640kbC++143.6kb2023-05-10 17:27:282023-05-10 17:27:29

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-10 17:27:29]
  • 评测
  • 测评结果:0
  • 用时:15ms
  • 内存:139640kb
  • [2023-05-10 17:27:28]
  • 提交

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%