QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#406054#8160. 切割zhicheng35 347ms171060kbC++141.6kb2024-05-06 19:29:072024-05-06 19:29:08

Judging History

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

  • [2024-05-06 19:29:08]
  • 评测
  • 测评结果:35
  • 用时:347ms
  • 内存:171060kb
  • [2024-05-06 19:29:07]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n,cnt,a[N],b[N],f[N],siz[N];
vector<int>v[N];
vector<pair<int,int> >p[N<<2];
struct s{
	int x,f,y;
};
stack<s>st;
int g(int x){
	if(f[x]!=x){
		return g(f[x]);
	}
	return x;
}
void merge(int x,int y){
	x=g(x);
	y=g(y);
	if(x!=y){
		cnt++;
		if(siz[x]>siz[y]){
			swap(x,y);
		}
		st.push({x,f[x],y});
		f[x]=y;
		siz[y]+=siz[x];
	}
}
void update(int x,int y,int a,int b,int l,int r,int rt){
	int mid=(l+r)>>1;
	if(x<=l&&y>=r){
		p[rt].push_back({a,b});
		return;
	}
	if(x<=mid){
		update(x,y,a,b,l,mid,rt<<1);
	}
	if(y>=mid+1){
		update(x,y,a,b,mid+1,r,rt<<1|1);
	}
}
void solve(int l,int r,int rt){
	int mid=(l+r)>>1,si=st.size();
	for(auto i:p[rt]){
		merge(i.first,i.second);
	}
	if(cnt==n-1){
		for(int i=l;i<=r;i++){
			printf("ymqOAO\n");
		}
		goto lass;
	}
	if(l==r){
		printf("Bob\n");
	}
	else{
		solve(l,mid,rt<<1);
		solve(mid+1,r,rt<<1|1);
	}
	lass:;
	while(st.size()>si){
		cnt--;
		f[st.top().x]=st.top().f;
		siz[st.top().y]-=siz[st.top().x];
		st.pop();
	}
}
int main(){
	int m,k,c,d;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		f[i]=i;
		siz[i]=1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a[i],&b[i]);
		v[i].push_back(0);
	}
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		scanf("%d",&c);
		while(c--){
			scanf("%d",&d);
			v[d].push_back(i);
		}
	}
	for(int i=1;i<=m;i++){
		v[i].push_back(k+1);
		for(int j=0;j<v[i].size()-1;j++){
			if(v[i][j]+1!=v[i][j+1]){
				update(v[i][j]+1,v[i][j+1]-1,a[i],b[i],1,k,1);
			}
		}
	}
	solve(1,k,1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 24ms
memory: 127828kb

input:

1500 2000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
49 5...

output:

Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
Bob
ymqOAO
Bob
Bob
ymqOAO
Bob
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
Bob
y...

result:

wrong answer 774th lines differ - expected: 'Bob', found: 'ymqOAO'

Test #2:

score: 5
Accepted
time: 19ms
memory: 129164kb

input:

1800 2000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
49 5...

output:

Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
ymqOAO
B...

result:

ok 1800 lines

Test #3:

score: 0
Time Limit Exceeded

input:

1000000 999999
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55...

output:


result:


Test #4:

score: 5
Accepted
time: 347ms
memory: 170388kb

input:

100000 99999
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
...

result:

ok 100000 lines

Test #5:

score: 5
Accepted
time: 171ms
memory: 150216kb

input:

90000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO...

result:

ok 90000 lines

Test #6:

score: 5
Accepted
time: 135ms
memory: 150024kb

input:

80000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
ymqOAO...

result:

ok 80000 lines

Test #7:

score: 0
Wrong Answer
time: 282ms
memory: 163592kb

input:

80000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
...

result:

wrong answer 76838th lines differ - expected: 'Bob', found: 'ymqOAO'

Test #8:

score: 5
Accepted
time: 315ms
memory: 166200kb

input:

90000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bo...

result:

ok 90000 lines

Test #9:

score: 0
Wrong Answer
time: 142ms
memory: 153160kb

input:

50000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOA...

result:

wrong answer 43658th lines differ - expected: 'Bob', found: 'ymqOAO'

Test #10:

score: 5
Accepted
time: 301ms
memory: 171060kb

input:

90000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
Bob
ymqOAO
Bob
Bob
Bo...

result:

ok 90000 lines

Test #11:

score: 0
Wrong Answer
time: 199ms
memory: 157336kb

input:

60000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

ymqOAO
Bob
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
Bob
Bob
ymqO...

result:

wrong answer 14521st lines differ - expected: 'Bob', found: 'ymqOAO'

Test #12:

score: 5
Accepted
time: 211ms
memory: 159588kb

input:

66000 100000
1 2
1 3
3 4
1 5
4 6
2 7
2 8
4 9
3 10
3 11
6 12
7 13
11 14
5 15
11 16
3 17
11 18
7 19
14 20
11 21
13 22
9 23
2 24
4 25
5 26
13 27
7 28
8 29
19 30
23 31
5 32
29 33
10 34
1 35
8 36
19 37
27 38
15 39
34 40
5 41
10 42
31 43
35 44
9 45
9 46
7 47
9 48
3 49
27 50
40 51
43 52
43 53
10 54
37 55
4...

output:

Bob
Bob
ymqOAO
ymqOAO
Bob
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
Bob
Bob
Bob
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
ymqOAO
ymqOAO
Bob
ymqOAO
ymqOAO
Bob
y...

result:

ok 66000 lines

Test #13:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
3 4
1 5
1 6
3 7
1 8
7 9
1 10
5 11
5 12
7 13
13 14
1 15
6 16
10 17
12 18
18 19
19 20
11 21
19 22
20 23
15 24
9 25
3 26
19 27
2 28
5 29
8 30
26 31
3 32
6 33
2 34
10 35
32 36
33 37
9 38
11 39
7 40
21 41
11 42
7 43
39 44
33 45
31 46
1 47
46 48
1 49
22 50
46 51
34 52
38 53
33 54
25...

output:


result:


Test #14:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
1 4
1 5
1 6
6 7
7 8
2 9
9 10
1 11
5 12
7 13
1 14
11 15
8 16
7 17
4 18
1 19
2 20
5 21
6 22
19 23
9 24
1 25
1 26
5 27
26 28
1 29
1 30
1 31
20 32
17 33
23 34
17 35
16 36
21 37
16 38
37 39
31 40
37 41
25 42
9 43
13 44
5 45
10 46
2 47
19 48
35 49
45 50
41 51
21 52
15 53
30 54
49 55...

output:


result:


Test #15:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
1 4
1 5
2 6
1 7
6 8
1 9
4 10
9 11
5 12
1 13
7 14
9 15
7 16
5 17
17 18
7 19
11 20
15 21
7 22
15 23
11 24
4 25
20 26
9 27
22 28
1 29
12 30
25 31
26 32
31 33
23 34
26 35
34 36
1 37
30 38
13 39
1 40
37 41
2 42
20 43
42 44
16 45
45 46
39 47
43 48
45 49
37 50
21 51
6 52
44 53
30 54
...

output:


result:


Test #16:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
1 4
1 5
3 6
3 7
5 8
1 9
2 10
8 11
10 12
11 13
1 14
11 15
13 16
1 17
13 18
7 19
7 20
19 21
19 22
1 23
7 24
9 25
11 26
17 27
15 28
7 29
1 30
18 31
27 32
26 33
1 34
27 35
2 36
13 37
20 38
19 39
10 40
1 41
17 42
29 43
1 44
25 45
19 46
7 47
12 48
1 49
37 50
31 51
1 52
23 53
42 54
1...

output:


result:


Test #17:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
3 4
4 5
5 6
1 7
6 8
7 9
4 10
1 11
10 12
4 13
1 14
6 15
6 16
1 17
9 18
13 19
16 20
9 21
15 22
12 23
16 24
3 25
3 26
15 27
15 28
9 29
27 30
3 31
16 32
13 33
19 34
30 35
3 36
13 37
8 38
37 39
16 40
28 41
9 42
9 43
43 44
33 45
7 46
41 47
3 48
41 49
4 50
21 51
3 52
17 53
2 54
39 55...

output:


result:


Test #18:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
1 4
3 5
4 6
1 7
1 8
2 9
1 10
5 11
2 12
5 13
5 14
11 15
1 16
15 17
17 18
7 19
16 20
18 21
1 22
13 23
14 24
16 25
7 26
7 27
16 28
22 29
11 30
1 31
25 32
17 33
1 34
2 35
27 36
36 37
9 38
28 39
19 40
1 41
15 42
22 43
36 44
4 45
42 46
39 47
21 48
21 49
15 50
21 51
1 52
45 53
8 54
1...

output:


result:


Test #19:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
1 4
1 5
4 6
3 7
7 8
3 9
4 10
1 11
9 12
7 13
2 14
1 15
4 16
3 17
13 18
1 19
1 20
15 21
16 22
7 23
19 24
17 25
15 26
14 27
10 28
21 29
8 30
1 31
21 32
9 33
19 34
23 35
1 36
29 37
30 38
15 39
28 40
35 41
41 42
1 43
11 44
6 45
20 46
23 47
44 48
13 49
34 50
49 51
35 52
38 53
36 54
...

output:


result:


Test #20:

score: 0
Time Limit Exceeded

input:

915000 1000000
1 2
1 3
3 4
1 5
2 6
3 7
2 8
1 9
4 10
5 11
8 12
1 13
8 14
5 15
11 16
7 17
7 18
18 19
14 20
9 21
17 22
8 23
11 24
13 25
1 26
11 27
15 28
1 29
17 30
1 31
29 32
28 33
1 34
5 35
15 36
19 37
13 38
17 39
35 40
1 41
5 42
25 43
2 44
27 45
1 46
13 47
3 48
33 49
22 50
35 51
36 52
14 53
32 54
16 ...

output:


result: