QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352003#2376. Game on a Treespiros_galWA 0ms3616kbC++143.5kb2024-03-12 19:14:582024-03-12 19:14:58

Judging History

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

  • [2024-03-12 19:14:58]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2024-03-12 19:14:58]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

4
1 2
2 3
3 4

output:

i=0 0
i=1 0
i=2 0
i=3 0
Bob

result:

wrong answer 1st lines differ - expected: 'Bob', found: 'i=0 0'