QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#182710#4896. Alice、Bob 与 DFSzhoukangyang0 3ms30144kbC++111.3kb2023-09-18 14:22:332023-09-18 14:22:34

Judging History

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

  • [2023-09-18 14:22:34]
  • 评测
  • 测评结果:0
  • 用时:3ms
  • 内存:30144kb
  • [2023-09-18 14:22:33]
  • 提交

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long 
#define vi vector < int > 
#define sz(a) ((int) (a).size())
#define ll long long 
#define ull unsigned long long
#define me(a, x) memset(a, x, sizeof(a)) 
using namespace std;
const int N = 1e6 + 7;
int n;
int c[N];
vi e[N];
int dp[N];
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	L(i, 1, n) {
		cin >> c[i];
	}
	L(i, 1, n) {
		int m;
		cin >> m;
		while(m--) {
			int x;
			cin >> x;
			e[i].emplace_back(x);
		}
	}
	R(i, n, 1) {
		if(c[i] == 0) {
			R(j, sz(e[i]) - 1, 0) {
				dp[i] ^= dp[e[i][j]];
			}
			dp[i] &= 1;
		} else {
			vi vc;
			R(j, sz(e[i]) - 1, 0) {
				int w = dp[e[i][j]];
				int l = 0, r = sz(vc) - 1, ans = sz(vc);
				while(l <= r) {
					int mid = (l + r) >> 1;
					if(w < vc[mid] - mid) ans = mid, r = mid - 1;
					else l = mid + 1;
				} 
				w += ans;
				vc.insert(lower_bound(vc.begin(), vc.end(), w), w);
			}
			dp[i] = 0;
			while(dp[i] < sz(vc) && vc[dp[i]] == dp[i]) ++dp[i];
		}
	}	
	int k;
	cin >> k;
	
	int ans = 0;
	while(k--) {
		int x;
		cin >> x;
		ans ^= dp[x];
	}
	if(ans == 0) cout << "Bob\n";
	else cout << "Alice\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

Bob

result:

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

Subtask #2:

score: 0
Wrong Answer

Test #18:

score: 15
Accepted
time: 3ms
memory: 28016kb

input:

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

output:

Bob

result:

ok "Bob"

Test #19:

score: -15
Wrong Answer
time: 0ms
memory: 30132kb

input:

6
0 1 0 0 1 0
2 2 6
3 3 4 5
0
0
0
0
1
1

output:

Alice

result:

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

Subtask #3:

score: 0
Wrong Answer

Test #55:

score: 15
Accepted
time: 0ms
memory: 28084kb

input:

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

output:

Bob

result:

ok "Bob"

Test #56:

score: -15
Wrong Answer
time: 0ms
memory: 28092kb

input:

6
0 1 0 0 1 0
2 2 6
3 3 4 5
0
0
0
0
1
1

output:

Alice

result:

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

Subtask #4:

score: 0
Wrong Answer

Test #103:

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

input:

10
1 1 1 1 1 1 1 1 1 1
1 2
4 3 5 7 8
1 4
0
1 6
0
0
1 9
1 10
0
1
1

output:

Bob

result:

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

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%