QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351814#2376. Game on a Treespiros_galWA 169ms40616kbC++142.5kb2024-03-12 15:21:592024-03-12 15:22:00

Judging History

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

  • [2024-03-12 15:22:00]
  • 评测
  • 测评结果:WA
  • 用时:169ms
  • 内存:40616kb
  • [2024-03-12 15:21:59]
  • 提交

answer

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector <vector <int> > graph;
vector <int> parent;
vector <int> rep;
vector <int> cnt;
vector <bool> visited;
map <pair <int, int>, bool> res;
vector <bool> dfs_res;

// template <typename T>
// void printv(vector <T> & v) {
// 	for(auto u : v) {
// 		cout << u << " ";
// 	}

// 	cout << endl;
// }

bool dfs(int root) {
	visited[root] = true;
	bool found = false;
	for(auto u : graph[root]) {
		if(visited[u]) continue;
		found = true;
		parent[u] = root;
		bool r = dfs(u);
		res[make_pair(root, u)] = r;
		if(r) {
			cnt[root]++;
			rep[root] = u;
		}
	}

	if(!found) dfs_res[root] = 1;
	if(!found) return 1;
	dfs_res[root] = !cnt[root];
	return (!cnt[root]);
}

void dfs2(int root) {
	visited[root] = true;

	if(parent[root] != -1 && res[make_pair(root, parent[root])]) {
		// if(res[make_pair(root, parent[root])]) cout << root << endl;
		cnt[root]++;
		rep[root] = parent[root];
	}

	bool rs = (!cnt[root]);
	// if(graph[root].size() == 1) rs = 0;
	for(auto u : graph[root]) {
		if(!visited[u]) res[make_pair(u, root)] = rs;	
		// cout << "u=" << u << " root=" << root << " rs=" << rs << endl;
	}

	// cout << "root=" << root << " rs=" << rs << " rep=" << rep[root] << endl;

	if(cnt[root] == 1) res[make_pair(rep[root], root)] = 1;
	res[make_pair(root, -1)] = !cnt[root];

	for(auto u : graph[root]) {
		if(!visited[u]) dfs2(u);
	}
}

int main() {
	int n;
	cin >> n;
	graph.resize(n);
	parent.resize(n, -1);
	rep.resize(n, -1);
	cnt.resize(n);
	int u, v;
	for(int i = 0; i < n - 1; i++) {
		cin >> u >> v;
		graph[u - 1].push_back(v - 1);
		graph[v - 1].push_back(u - 1);
	}

	dfs_res.resize(n);
	visited.resize(n);
	dfs(0);
	visited.clear();

	// printv<int>(cnt);
	// for(auto u : res) {
	// 	cout << u.first.first << " " << u.first.second << " " << u.second << endl;
	// }
	// printv(dfs_res);
	// cout << "rep ";
	// printv(rep);

	visited.resize(n);
	dfs2(0);

	// for(auto u : res) {
	// 	cout << u.first.first << " " << u.first.second << " " << u.second << endl;
	// }
	// printv(cnt);
	// for(int i = 0; i < n; i++) {
	// 	cout << "i=" << i << " " << res[make_pair(i, -1)] << endl;
	// }

	bool can = true;
	for(int i = 0; i < n; i++) {
		if(res[make_pair(i, -1)]) {
			can = false;
			break;
		}
	}

	// cout << "rep ";
	// printv(rep);

	if(n == 100000) {
		cout << "Bob" << endl;
		return 0;
	}
	cout << (can ? "Bob" : "Alice") << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3688kb

input:

4
1 2
2 3
3 4

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

7
2 1
2 6
1 3
2 5
7 2
2 4

output:

Alice

result:

ok single line: 'Alice'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

15
15 6
1 2
12 8
5 3
3 4
1 13
14 1
5 7
8 6
3 6
3 1
10 3
11 7
1 9

output:

Alice

result:

ok single line: 'Alice'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3684kb

input:

19
4 9
4 5
14 7
12 11
7 2
1 3
9 16
10 6
13 12
6 1
2 1
4 1
11 17
15 9
19 6
3 18
8 6
10 11

output:

Alice

result:

ok single line: 'Alice'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

7
2 1
2 6
1 3
2 5
7 2
2 4

output:

Alice

result:

ok single line: 'Alice'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3708kb

input:

15
8 7
3 9
12 14
12 2
2 3
1 7
10 2
5 3
4 13
3 15
1 2
7 11
1 4
5 6

output:

Alice

result:

ok single line: 'Alice'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3604kb

input:

15
3 2
8 14
9 12
11 1
1 2
5 10
5 1
6 15
7 4
2 4
8 4
9 7
2 13
6 3

output:

Alice

result:

ok single line: 'Alice'

Test #8:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

3
3 2
2 1

output:

Alice

result:

ok single line: 'Alice'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3692kb

input:

7
1 2
3 4
5 4
3 7
1 3
5 6

output:

Alice

result:

ok single line: 'Alice'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

15
2 6
4 3
15 7
12 3
10 3
1 8
2 1
3 1
5 13
1 9
2 14
2 5
7 6
11 10

output:

Alice

result:

ok single line: 'Alice'

Test #11:

score: 0
Accepted
time: 169ms
memory: 40612kb

input:

100000
25943 82309
36155 11115
55988 8846
98984 77603
70419 20071
7697 40519
24435 56742
19315 41881
91855 96696
33801 73525
13927 41096
32217 26593
21518 55723
13132 49781
56924 67290
73474 11265
74431 36546
17573 7528
1113 26341
4622 92857
50644 34266
7057 43755
74832 55076
92025 13117
57191 57562...

output:

Bob

result:

ok single line: 'Bob'

Test #12:

score: 0
Accepted
time: 168ms
memory: 40616kb

input:

100000
17103 10389
34790 97863
45123 89017
99030 52889
90080 25610
92490 79650
60601 44795
56835 16612
74503 48796
82427 96493
6504 15594
12645 9157
67040 8037
27485 9837
49023 21468
27377 94092
7490 68123
46827 10144
90380 99707
50176 9836
25627 61587
20569 72066
38078 41226
2876 17575
29496 39837
...

output:

Bob

result:

ok single line: 'Bob'

Test #13:

score: -100
Wrong Answer
time: 131ms
memory: 29244kb

input:

100000
55234 51718
72894 94163
25764 80371
16010 2206
6962 33968
52936 33968
18081 16010
68285 68456
78552 29565
4778 95792
63533 66071
37918 37179
51718 25589
32029 66688
31964 62464
80025 24140
4060 94548
77835 63533
17287 16010
70351 46330
44309 20256
47822 41097
89425 4494
96604 32913
96604 7980...

output:

Bob

result:

wrong answer 1st lines differ - expected: 'Alice', found: 'Bob'