Submission #138573

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
138573	2019-07-30T07:07:22 Z	윤교준(#3320)	Graphic Madness (CERC12_K)	C++14	0 / 1	1000 ms	8984 KB

K

#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();
      ~~~~~^~~~~~~~~~

Subtask #1

0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1070 ms	8984 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-