#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define rb(x) ((x)&(-(x)))
using namespace std;
typedef pair<int, int> pii;
struct TRE {
vector<int> G[2005];
int prt[11][2005], dep[2005];
bitset<2005> chk;
vector<pii> W;
int N, K;
void init() {
chk.reset(); W.clear();
for(int i = 1; i <= N; i++) G[i].clear();
memset(dep, 0, (N+1)<<2);
N = K = 0;
}
void add(int a, int b) { G[a].eb(b); G[b].eb(a); }
int lca(int a, int b) {
if(dep[a] > dep[b]) swap(a, b);
const int dt = dep[b] - dep[a];
for(int i = 11; i--;) if(dt & (1<<i))
b = prt[i][b];
if(a == b) return a;
for(int i = 11; i--;) if(prt[i][a] != prt[i][b]) {
a = prt[i][a];
b = prt[i][b];
}
return prt[0][a];
}
void getPath(vector<int> &V, int a, int b) {
int c = lca(a, b);
vector<int> T;
for(;;) {
V.eb(a);
if(a == c) break;
a = prt[0][a];
}
for(;;) {
if(b == c) break;
T.eb(b);
b = prt[0][b];
}
revv(T);
for(int t : T) V.eb(t);
}
bool isp(int a, int b) {
int c = lca(a, b);
for(;;) {
if(chk[a]) return false;
if(a == c) break;
a = prt[0][a];
}
for(;;) {
if(chk[b]) return false;
if(b == c) break;
b = prt[0][b];
}
return true;
}
void upd(int a, int b) {
W.eb(a, b);
int c = lca(a, b);
for(;;) {
chk[a] = true;
if(a == c) break;
a = prt[0][a];
}
for(;;) {
chk[b] = true;
if(b == c) break;
b = prt[0][b];
}
}
void dfs(int i) {
for(int v : G[i]) if(!dep[v]) {
dep[v] = dep[i] + 1;
prt[0][v] = i;
dfs(v);
}
}
void run() {
dep[N] = 1; dfs(N);
for(int j = 1; j < 11; j++) for(int i = 1; i <= N; i++)
prt[j][i] = prt[j-1][prt[j-1][i]];
vector<pii> EV;
for(int i = 1; i < K; i++) for(int j = i+1; j <= K; j++) {
int c = lca(i, j);
int l = dep[i] + dep[j] - (dep[c] << 1);
EV.eb(l, i<<12|j);
}
sorv(EV);
for(auto &ev : EV) {
int a = ev.second, b;
b = a >> 12; a ^= b << 12;
if(isp(a, b)) upd(a, b);
}
}
} treA, treB;
int PA[1005], PB[1005]; // A <-> A, B <-> B
int LA[1005], LB[1005]; // A <-> B
bitset<2005> chkA, chkB;
int T, N, M, K;
void run() {
scanf("%d%d%d", &K, &N, &M);
treA.init(); treB.init();
treA.N = N+K; treA.K = K;
treB.N = M+K; treB.K = K;
for(int _ = N+K-1, a, b; _--;) {
char ca, cb;
scanf(" A%c%d A%c%d", &ca, &a, &cb, &b);
if('P' == ca) a += K;
if('P' == cb) b += K;
treA.add(a, b);
}
for(int _ = M+K-1, a, b; _--;) {
char ca, cb;
scanf(" B%c%d B%c%d", &ca, &a, &cb, &b);
if('P' == ca) a += K;
if('P' == cb) b += K;
treB.add(a, b);
}
for(int _ = K, a, b; _--;) {
char ca, cb;
scanf(" %cS%d %cS%d", &ca, &a, &cb, &b);
if(ca == 'B') swap(a, b);
LA[a] = b; LB[b] = a;
}
if(K&1) {
puts("NO");
return;
}
treA.run(); treB.run();
{
auto V = treA.W;
if(sz(V) != (K>>1)) {
puts("NO");
return;
}
for(auto &v : V) {
int a, b; tie(a, b) = v;
PA[a] = b;
PA[b] = a;
}
}
{
auto V = treB.W;
if(sz(V) != (K>>1)) {
puts("NO");
return;
}
for(auto &v : V) {
int a, b; tie(a, b) = v;
PB[a] = b;
PB[b] = a;
}
}
chkA.reset(); chkB.reset();
vector<pii> Path;
for(int v = 1, p;;) {
if(chkA[v]) break;
{
vector<int> V;
p = PA[v];
treA.getPath(V, v, p);
for(int w : V) {
if(chkA[w]) {
puts("NO");
return;
}
chkA[w] = true;
Path.eb(0, w);
}
v = p;
}
v = LA[v];
if(chkB[v]) break;
{
vector<int> V;
p = PB[v];
treB.getPath(V, v, p);
for(int w : V) {
if(chkB[w]) {
puts("NO");
return;
}
chkB[w] = true;
Path.eb(1, w);
}
v = p;
}
v = LB[v];
}
if(sz(Path) != N+M+K+K) {
puts("NO");
return;
}
printf("YES ");
for(auto &v : Path) {
int a, b; tie(a, b) = v;
putchar(a ? 'B' : 'A');
if(K < b) {
putchar('P');
b -= K;
} else putchar('S');
printf("%d ", b);
}
puts("");
}
int main() {
for(scanf("%d", &T); T--;) run();
return 0;
}
Compilation message
K.cpp: In function 'void run()':
K.cpp:122:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &K, &N, &M);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
K.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" A%c%d A%c%d", &ca, &a, &cb, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
K.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" B%c%d B%c%d", &ca, &a, &cb, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
K.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %cS%d %cS%d", &ca, &a, &cb, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
K.cpp: In function 'int main()':
K.cpp:238:11: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(scanf("%d", &T); T--;) run();
~~~~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1070 ms |
8984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
