QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351758#2376. Game on a Treespiros_galWA 185ms40644kbC++142.4kb2024-03-12 14:38:592024-03-12 14:38:59

Judging History

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

  • [2024-03-12 14:38:59]
  • 评测
  • 测评结果:WA
  • 用时:185ms
  • 内存:40644kb
  • [2024-03-12 14:38: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);

	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: 3700kb

input:

4
1 2
2 3
3 4

output:

Bob

result:

ok single line: 'Bob'

Test #2:

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

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: 3644kb

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: 3700kb

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: 3640kb

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: 3644kb

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: 3704kb

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: 3636kb

input:

3
3 2
2 1

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

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: 3588kb

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: -100
Wrong Answer
time: 185ms
memory: 40644kb

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:

Alice

result:

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