Submission #138533

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138533	2019-07-30T06:33:01 Z	김세빈(#3318)	Graphic Madness (CERC12_K)	C++14	1 / 1	54 ms	1144 KB

K

#include <bits/stdc++.h>

#define die() { printf("NO\n"); return; }

using namespace std;

struct tree{
	vector <int> T[2020];
	vector <int> P[2020];
	int C1[2020], C2[2020];
	
	void clear(int n)
	{
		int i;
		
		for(i=1; i<=n; i++){
			T[i].clear(); P[i].clear();
			C1[i] = C2[i] = 0;
		}
	}
	
	void addedge(int x, int y)
	{
		T[x].push_back(y);
		T[y].push_back(x);
	}
	
	void connect(int x, int y) { C2[x] = y; }
	
	int dfs(int p, int r)
	{
		vector <int> X;
		int x, y, v, f;
		
		x = y = -1; f = 0;
		
		for(int &t: T[p]){
			if(t != r){
				f = 1; v = dfs(t, p);
				if(v == -1) return -1;
				else if(v){
					P[v].push_back(p);
					if(x == -1) x = v;
					else if(y == -1) y = v;
					else return -1;
				}
			}
		}
		
		if(x == -1){
			if(f) return -1;
			else return p;
		}
		else if(y == -1) return x;
		else{
			C1[x] = y, C1[y] = x;
			return 0;
		}
	}
	
	int makepath(int p, vector <int> &V, int c)
	{
		V.push_back(p + c);
		for(int &t: P[p]) V.push_back(t + c);
		
		p = C1[p]; P[p].pop_back();
		reverse(P[p].begin(), P[p].end());
		
		for(int &t: P[p]) V.push_back(t + c);
		V.push_back(p + c);
		
		return C2[p];
	}
	
	void print(int n)
	{
		int i;
		
		for(i=1; i<=n; i++){
			printf("%d : ", i);
			for(int &t: P[i]) printf("%d ", t);
			printf("\n");
		}
	}
};

tree A, B;
int n, m, k;

int read()
{
	char S[11];
	char c1, c2; int v;
	
	scanf("%s", S);
	sscanf(S, "%c%c%d", &c1, &c2, &v);
	
	if(c2 == 'P') v += k;
	if(c1 == 'B') v += n + k;
	
	return v; 
}

void print(int v)
{
	if(v > n + k) printf(" B"), v -= n + k;
	else printf(" A");
	
	if(v > k) printf("P"), v -= k;
	else printf("S");
	
	printf("%d", v);
}

void tc()
{
	vector <int> V;
	int i, x, y;
	
	scanf("%d%d%d", &k, &n, &m);
	
	A.clear(n + k); B.clear(m + k);
	
	for(i=1; i<n+k; i++){
		x = read(); y = read();
		A.addedge(x, y);
	}
	
	for(i=1; i<m+k; i++){
		x = read(); y = read();
		x -= n + k; y -= n + k;
		B.addedge(x, y);
	}
	
	for(i=1; i<=k; i++){
		x = read(); y = read();
		if(x > n + k) swap(x, y); y -= n + k;
		A.connect(x, y); B.connect(y, x);
	}
	
	if(A.dfs(k + 1, 0) == -1) die();
	if(B.dfs(k + 1, 0) == -1) die();
	
//	A.print(k); B.print(k);
	
	for(i=1; ; ){
		i = A.makepath(i, V, 0);
		i = B.makepath(i, V, n + k);
		if(i == 1) break;
	}
	
	if(V.size() != n + m + k + k) die();
	
	printf("YES");
	
	for(int &t: V){
		print(t);
	}
	
	printf("\n");
}

int main()
{
	int t;
	
	scanf("%d", &t);
	
	for(; t--; ){
		tc();
	}
	
	return 0;
}

Compilation message

K.cpp: In function 'void tc()':
K.cpp:137:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   if(x > n + k) swap(x, y); y -= n + k;
   ^~
K.cpp:137:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   if(x > n + k) swap(x, y); y -= n + k;
                             ^
K.cpp:152:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(V.size() != n + m + k + k) die();
     ~~~~~~~~~^~~~~~~~~~~~~~~~
K.cpp: In function 'int read()':
K.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", S);
  ~~~~~^~~~~~~~~
K.cpp: In function 'void tc()':
K.cpp:120: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: In function 'int main()':
K.cpp:167:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
  ~~~~~^~~~~~~~~~

Subtask #1

1.0 / 1.0

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