QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104422#185. Bridgesfzj20070 50ms173976kbC++143.7kb2023-05-10 17:34:022023-05-10 17:34:05

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:34:05]
  • 评测
  • 测评结果:0
  • 用时:50ms
  • 内存:173976kb
  • [2023-05-10 17:34:02]
  • 提交

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%