Submission #552221

#	Time	Username	Problem	Language	Result	Execution time	Memory
552221		LucaDantas	Jail (JOI22_jail)	C++17	21 / 100	5084 ms	396 KiB

jail

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 251, maxm = 6;

int p[maxn], depth[maxn];
vector<int> g[maxn];

void dfs(int u) {
	for(int v : g[u]) if(v != p[u]) {
		p[v] = u;
		depth[v] = depth[u] + 1;
		dfs(v);
	}
}

void clear(int n) {
	for(int i = 0; i <= n; i++)
		g[i].clear(), p[i] = 0, depth[i] = 0;
}

int s[maxm], t[maxm];
bool mark[maxn];

bool fine(int a, int b) {
	bool ok = !mark[b]; // b é pra ser meu final, se tem alguém la já fudeu
	// pode ter gente no a que no caso sou eu mesmo
	// printf("comeco %d %d\n", a, b);
	for(; a != b;) {
		if(depth[a] < depth[b])
			swap(a, b);
		a = p[a];
		ok &= !mark[a];
		// printf("%d %d\n", a, b);
	}
	// printf("fim %d\n", ok);
	return ok;
}

int main() {
	int q; scanf("%d", &q);
	while(q--) {
		int n; scanf("%d", &n);
		clear(n);
		for(int i = 1, a, b; i < n; i++)
			scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
		dfs(1);
		int m; scanf("%d", &m);
		for(int i = 0; i < m; i++)
			scanf("%d %d", s+i, t+i);
		vector<int> ord(m); iota(ord.begin(), ord.end(), 0);
		bool ans = 0;
		do {
			bool ok = 1;
			for(int i = 0; i < m; i++)
				mark[s[i]] = 1;
			for(int i = 0; i < m; i++) {
				int now = ord[i];
				mark[s[now]] = 0;
				ok &= fine(s[now], t[now]);
				mark[t[now]] = 1;
			}
			for(int i = 0; i < m; i++)
				mark[t[i]] = 0;
			ans |= ok;
			// puts("PROXIMA\n");
		} while(next_permutation(ord.begin(), ord.end()));
		puts(ans ? "Yes" : "No");
	}
}

Compilation message (stderr)

jail.cpp: In function 'int main()':
jail.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |  int q; scanf("%d", &q);
      |         ~~~~~^~~~~~~~~~
jail.cpp:43:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   int n; scanf("%d", &n);
      |          ~~~~~^~~~~~~~~~
jail.cpp:46:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |    scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
      |    ~~~~~^~~~~~~~~~~~~~~~~
jail.cpp:48:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   int m; scanf("%d", &m);
      |          ~~~~~^~~~~~~~~~
jail.cpp:50:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |    scanf("%d %d", s+i, t+i);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23