QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352006#2376. Game on a Treespiros_galWA 219ms28800kbC++143.5kb2024-03-12 19:15:542024-03-12 19:15:54

Judging History

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

  • [2024-03-12 19:15:54]
  • 评测
  • 测评结果：WA
  • 用时：219ms
  • 内存：28800kb
查看
  • [2024-03-12 19:15:54]
  • 提交

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;
// 		}
// 	}

// 	return (!cnt[root]);
// }

void dfs(int root) {
	stack <int> st;
	st.push(root);
	while(!st.empty()) {
		root = st.top();
		visited[root] = true;
		bool found = false;
		for(auto u : graph[root]) {
			if(visited[u]) continue;
			found = true;
			parent[u] = root;
			st.push(u);
		}

		if(!found) {
			st.pop();
			for(auto u : graph[root]) {
				if(u != parent[root]) {
					bool r = dfs_res[u];
					res[make_pair(root, u)] = r;
					if(r) {
						cnt[root]++;
						rep[root] = u;
					}
				}
			}
			
			dfs_res[root] = !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);
// 	}
// }

void dfs2(int root) {
	stack<int> st;
	st.push(root);

	while(!st.empty()) {
		int root = st.top();
		st.pop();
		visited[root] = true;
		if(parent[root] != -1 && res[make_pair(root, parent[root])]) {
			cnt[root]++;
			rep[root] = parent[root];
		}

		bool rs = !cnt[root];
		for(auto u : graph[root]) {
			if(!visited[u]) res[make_pair(u, root)] = rs;
		}

		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]) st.push(u);
		}
	}
}

int main() {
	int n;
	cin >> n;
	graph.resize(n);
	parent.resize(n, -1);
	rep.resize(n, -1);
	cnt.resize(n);
	dfs_res.resize(n, 1);
	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);
	}

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

	// printv<int>(cnt);
	// for(auto u : res) {
	// 	cout << u.first.first << " " << u.first.second << " " << u.second << endl;
	// }
	// 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;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3528kb

input:

4
1 2
2 3
3 4

output:

Bob

result:

ok single line: 'Bob'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3544kb

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

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: 1ms
memory: 3788kb

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

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

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: 1ms
memory: 3612kb

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

input:

3
3 2
2 1

output:

Alice

result:

ok single line: 'Alice'

Test #9:

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

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

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: 219ms
memory: 28800kb

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'
English 繁體中文 简体中文

Server Time: 2024-11-30 00:31:30 | OpenSource Project