I have a solution I think is correct but can't get it to pass, and apparently even my n^2 code (standard game theory iterating through all states solution) that should obviously work gets WA. They both give the same answers for random small inputs.
I can't find editorials or test data for the contest, so seeing so many teams have +1 or more in this problem, is there some tricky corner case I might have missed?
My code if it is of any interest:
code
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = (int)1e9 + 7;
bool findCycle(int i, vector<int>& cycle, vector<int>& par, const vector<vector<int>>& conns) {
for (auto t : conns[i]) {
if (par[i] == t) continue;
if (par[t] != -1) {
if (par[t] == i) swap(t, i);
while(i != t) {
cycle.push_back(i);
i = par[i];
}
cycle.push_back(i);
return true;
} else {
par[t] = i;
bool found = findCycle(t, cycle, par, conns);
if (found) return true;
}
}
return false;
}
void dfs(int i, vector<int>& par, vector<int>& ban, const vector<vector<int>>& conns) {
for (auto t : conns[i]) {
if (par[t] != -1) continue;
if (ban[t] != -1) continue;
par[t] = i;
dfs(t, par, ban, conns);
}
}
vector<int> getDists(int s, const vector<vector<int>>& conns) {
int n = conns.size();
vector<int> dist(n, INF);
dist[s] = 0;
vector<int> que = {s};
for (int j = 0; j < que.size(); ++j) {
int i = que[j];
for (auto t : conns[i]) {
if (dist[t] == INF) {
dist[t] = dist[i] + 1;
que.push_back(t);
}
}
}
return dist;
}
int findClosest(const vector<int>& list, const vector<int>& dist) {
int rd = INF;
int ri = -1;
for (int i = 0; i < list.size(); ++i) {
if (dist[list[i]] < rd) {
rd = dist[list[i]];
ri = i;
}
}
return ri;
}
void solve(int ti) {
int n;
cin >> n;
vector<vector<int>> conns(n);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
conns[a].push_back(b);
conns[b].push_back(a);
}
int m;
cin >> m;
vector<int> dest(m);
for (int i = 0; i < m; ++i) {
cin >> dest[i];
--dest[i];
}
int a, b;
cin >> a >> b;
--a; --b;
vector<int> cycle;
vector<int> par(n, -1);
par[0] = 0;
findCycle(0, cycle, par, conns);
int k = cycle.size();
vector<int> cyc_ind(n, -1);
for (int j = 0; j < k; ++j) cyc_ind[cycle[j]] = j;
// See if A can win without doing anything related to the cycle
bool win = false;
vector<int> a_dists = getDists(a, conns);
vector<int> b_dists = getDists(b, conns);
for (auto i : dest) {
if (a_dists[i] <= b_dists[i]) win = true;
}
// See if A can win by playing in the cycle
if (! win) {
for (int i = 0; i < n; ++i) par[i] = -1;
for (auto i : cycle) {
par[i] = i;
dfs(i, par, cyc_ind, conns);
}
// cyc_win[i] = true for i in cycle if branch leading to win starts from i
vector<bool> cyc_win(n, false);
for (auto i : dest) {
for (int j = i; !cyc_win[j]; j = par[j]) {
cyc_win[j] = true;
}
}
// Find closest nodes in cycle for a and b
int cai = findClosest(cycle, a_dists);
int cbi = findClosest(cycle, b_dists);
int ca = cycle[cai];
int cb = cycle[cbi];
int da = a_dists[ca];
int db = b_dists[cb];
// Find closest cyc_win to the left and to the right of ca
int le_win = -1;
int ri_win = -1;
for (int j = cai;; j = (j-1+k)%k) {
if (cyc_win[cycle[j]]) {
le_win = j;
break;
}
}
for (int j = cai;; j = (j+1)%k) {
if (cyc_win[cycle[j]]) {
ri_win = j;
break;
}
}
// A
// |da
// x - x - x
// | da1 | da2
// lw rw
// | db1 | db2
// x - x - x
// | db
// B
int da1 = (cai - le_win + k) % k;
int da2 = (ri_win - cai + k) % k;
int db1 = (le_win - cbi + k) % k;
int db2 = (cbi - ri_win + k) % k;
if (db1 + db2 > k) {
// A and B are on the same side
// We need to figure out which side of A B is in
db1 = (k - db1) % k;
db2 = (k - db2) % k;
int dab = abs(da1 - db1);
if (db + dab < da) {
win = false; // B can block A from entering cycle
} else {
if (db1 <= da1) {
if (db + (k - db2) < da + da2) {
win = false; // B can go all the way around
} else {
win = true;
}
} else {
if (db + (k - db1) < da + da1) {
win = false; // B can go all the way around
} else {
win = true;
}
}
}
} else {
// A and B are on opposite sides
if (db + min(da1 + db1, da2 + db2) < da) {
win = false; // B can block A from entering cycle
} else if (le_win == ri_win) {
win = false; // Block messages
} else {
// Can B get into a position where it can get to
int ddif1 = db1 - da1 + 1; // Move this many times left for standstill
int ddif2 = db2 - da2 + 1; // Move this many times right for standstill
if (ddif1 + ddif2 <= 0 && min(0, max(ddif1, ddif2)) + db <= da) {
win = false; // B can get to standstill
} else {
win = true; // A can escape standstill
}
}
}
}
// Output result
cout << "Case " << (ti+1) << ": ";
if (win) cout << "Panda" << '\n';
else cout << "Sheep\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int ti = 0; ti < t; ++ti) solve(ti);
}
n^2 code
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int INF = (int)1e9 + 7;
const int N = 1010;
int win[2][N][N];
int rem[2][N][N];
vector<pair<int, pair<int, int>>> que;
void resolve(int s, int i, int j, int r) {
if (rem[s][i][j] <= 0) return;
win[s][i][j] = r;
rem[s][i][j] = 0;
que.push_back({s, {i, j}});
}
void solve(int ti) {
int n;
cin >> n;
que.clear();
for (int s = 0; s < 2; ++s) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
win[s][i][j] = 0;
rem[s][i][j] = 0;
}
}
}
vector<vector<int>> conns(n);
for (int i = 0; i < n; ++i) {
int a, b;
cin >> a >> b;
--a; --b;
conns[a].push_back(b);
conns[b].push_back(a);
}
for (int i = 0; i < n; ++i) conns[i].push_back(i);
int m;
cin >> m;
vector<int> dest(m);
for (int i = 0; i < m; ++i) {
cin >> dest[i];
--dest[i];
}
int a, b;
cin >> a >> b;
--a; --b;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
rem[0][i][j] = conns[i].size();
rem[1][i][j] = conns[j].size();
}
}
for (auto i : dest) {
for (int j = 0; j < n; ++j) {
resolve(0, i, j, 1);
if (i != j) resolve(1, i, j, 1);
}
}
for (int i = 0; i < n; ++i) {
resolve(1, i, i, -1);
}
for (int x = 0; x < que.size(); ++x) {
int s = que[x].first;
int i = que[x].second.first;
int j = que[x].second.second;
int r = (s ? 1 : -1);
if (s == 0) {
if (win[s][i][j] == r) {
for (auto t : conns[j]) {
resolve(s^1, i, t, r);
}
} else {
for (auto t : conns[j]) {
if (rem[s^1][i][t] == 1) resolve(s^1, i, t, -r);
else --rem[s^1][i][t];
}
}
} else {
if (win[s][i][j] == r) {
for (auto t : conns[i]) {
resolve(s^1, t, j, r);
}
} else {
for (auto t : conns[i]) {
if (rem[s^1][t][j] == 1) resolve(s^1, t, j, -r);
else --rem[s^1][t][j];
}
}
}
}
// Output result
bool ans = (win[0][a][b] == 1);
cout << "Case " << (ti+1) << ": ";
if (ans) cout << "Panda" << '\n';
else cout << "Sheep\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for (int ti = 0; ti < t; ++ti) solve(ti);
}
Do recheck — it seems to me that testdata is visible in coach mode. In particular, your code seems to fail on following case:
1 14 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 1 1 12 12 13 13 14 2 5 10 14 9
Okay, it looks like it matters that A cannot move into nodes that B has visited, I thought it was enough to check that A doesn't move into the node B is currently in. The brute-force code had the same assumption, so no wonder they gave the same answers.
Thank you, I found the issue now. A small change and the code gets accepted :) 54563432