Submission #138551

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138551	2019-07-30T06:48:37 Z	임유진(#3321)	Graphic Madness (CERC12_K)	C++14	1 / 1	30 ms	1148 KB

K

#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++) {
                    ~~^~~~~~~~~~~~~~~~

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	30 ms	1148 KB	Output is correct
2	Correct	30 ms	1144 KB	Output is correct