#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int chartonum(char c[]) {
int ans = 0;
for(int i = 0; c[i]; i++) ans = ans * 10 + c[i] - '0';
return ans;
}
struct CARD {
int K, N;
int par[MAXN], sz[MAXN], dep[MAXN], way[MAXN];
vector<int> ed[MAXN];
char name;
void init(int k, int n, char c) {
K = k;
N = n;
name = c;
for(int i = 1; i <= N + K; i++) ed[i].clear();
}
void input() {
for(int i = 0; i < N + K - 1; i++) {
char inp[2][10];
cin >> inp[0] >> inp[1];
int x = chartonum(inp[0] + 2), y = chartonum(inp[1] + 2);
if(inp[0][1] == 'S') x += N;
else if(inp[1][1] == 'S') y += N;
//printf("input by %c (%d, %d)\n", name, x, y);
ed[x].push_back(y);
ed[y].push_back(x);
}
}
void dfs(int x) {
sz[x] = x > N ? 1 : 0;
for(auto a : ed[x]) if(a != par[x]) {
par[a] = x;
dep[a] = dep[x] + 1;
dfs(a);
sz[x] += sz[a];
}
}
int solve(int x, bool up) {
vector<int> odd;
//printf("solve(x = %d, up = %d)\n", x, int(up));
if(x > N) return up ? x : -1;
for(auto a : ed[x]) if(a != par[x] && sz[a] % 2) odd.push_back(a);
if(up) {
if(odd.size() != 1) return -1;
for(auto a : ed[x]) if(a != par[x] && a != odd[0] && solve(a, false) == -1) return -1;
return solve(odd[0], true);
}
else {
if(odd.size() != 2) return -1;
int t1 = solve(odd[0], true), t2 = solve(odd[1], true);
if(t1 == -1 || t2 == -1) return -1;
//printf("solve(%d) = %d, solve(%d) = %d\n", odd[0], t1, odd[1], t2);
way[t1] = t2;
way[t2] = t1;
for(auto a : ed[x]) if(a != par[x] && a != odd[0] && a != odd[1] && solve(a, false) == -1) return -1;
return 0;
}
}
void move(int s1, int s2) {
cout << name << "S" << s1 << " ";
int x = par[s1 + N], y = par[s2 + N];
deque<int> p1, p2;
while(x != y) {
if(dep[x] > dep[y]) {
p1.push_back(x);
x = par[x];
}
else if(dep[x] < dep[y]) {
p2.push_front(y);
y = par[y];
}
else {
p1.push_back(x);
x = par[x];
p2.push_front(y);
y = par[y];
}
}
for(auto a : p1) cout << name << "P" << a << " ";
cout << name << "P" << x << " ";
for(auto a : p2) cout << name << "P" << a << " ";
cout << name << "S" << s2 << " ";
}
} A, B;
vector<int> btw[MAXN];
vector<int> ans;
bool chk[MAXN];
int main() {
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--) {
int K, N, M;
cin >> K >> N >> M;
A.init(K, N, 'A');
B.init(K, M, 'B');
for(int i = 1; i <= 2 * K; i++) btw[i].clear();
A.input();
B.input();
for(int i = 0; i < K; i++) {
char inp[2][10];
cin >> inp[0] >> inp[1];
//printf("[%s][%s] ", inp[0], inp[1]);
int x = chartonum(inp[0] + 2), y = chartonum(inp[1] + 2);
//printf("x = %d, y = %d\n", x, y);
if(inp[0][0] == 'B') swap(x, y);
btw[x].push_back(y + K);
btw[y + K].push_back(x);
}
/*
for(int i = 1; i <= N; i++) {
for(auto a : A.ed[i]) printf("%d ", a);
printf("\n");
}
printf("\n");
for(int i = 1; i <= M; i++) {
for(auto a : B.ed[i]) printf("%d ", a);
printf("\n");
}
*/
A.dfs(1);
//printf("input done\n");
B.dfs(1);
if(A.solve(1, false) == -1 || B.solve(1, false) == -1) cout << "NO\n";
else {
//printf("doing YES\n");
ans.clear();
for(int i = 1; i <= K; i++) {
//printf("A.way[%d] = %d\nB.way[%d] = %d\n", i + N, A.way[i + N], i + M, B.way[i + M]);
btw[i].push_back(A.way[i + N] - N);
btw[i + K].push_back(B.way[i + M] - M + K);
chk[i] = chk[i + K] = false;
}
for(int t = 1; !chk[t]; ) {
chk[t] = true;
//printf("t = %d\n", t);
ans.push_back(t);
if(chk[btw[t][0]]) t = btw[t][1];
else t = btw[t][0];
}
if(ans.size() < 2 * K) cout << "NO\n";
else {
cout << "YES ";
//for(auto a : ans) printf("(%d)", a);
ans.push_back(ans[0]);
for(int i = 0; i < ans.size() - 1; i++) {
//printf("(%d, %d)\n", ans[i], ans[i + 1]);
if(ans[i] <= K && ans[i + 1] <= K) A.move(ans[i], ans[i + 1]);
else if(ans[i] > K && ans[i + 1] > K) B.move(ans[i] - K, ans[i + 1] - K);
}
cout << "\n";
}
}
}
return 0;
}
Compilation message
K.cpp: In function 'int main()':
K.cpp:155:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(ans.size() < 2 * K) cout << "NO\n";
~~~~~~~~~~~^~~~~~~
K.cpp:160:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < ans.size() - 1; i++) {
~~^~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
30 ms |
1148 KB |
Output is correct |
| 2 |
Correct |
30 ms |
1144 KB |
Output is correct |
