oj.uz

Submission #552221

# Submission time Handle Problem Language Result Execution time Memory
552221 2022-04-22T19:16:05 Z LucaDantas Jail (JOI22_jail) C++17
21 / 100
 5000 ms 396 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 340 KB Output is correct
5 Correct 25 ms 312 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 19 ms 324 KB Output is correct
8 Execution timed out 5078 ms 212 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 308 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 308 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 21 ms 340 KB Output is correct
17 Correct 3 ms 328 KB Output is correct
18 Correct 12 ms 352 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 11 ms 340 KB Output is correct
21 Correct 5 ms 340 KB Output is correct
22 Correct 8 ms 340 KB Output is correct
23 Correct 3 ms 308 KB Output is correct
24 Correct 2 ms 212 KB Output is correct
25 Correct 15 ms 212 KB Output is correct
26 Correct 4 ms 312 KB Output is correct
27 Correct 5 ms 340 KB Output is correct
28 Correct 3 ms 212 KB Output is correct

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 308 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 21 ms 340 KB Output is correct
17 Correct 3 ms 328 KB Output is correct
18 Correct 12 ms 352 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 11 ms 340 KB Output is correct
21 Correct 5 ms 340 KB Output is correct
22 Correct 8 ms 340 KB Output is correct
23 Correct 3 ms 308 KB Output is correct
24 Correct 2 ms 212 KB Output is correct
25 Correct 15 ms 212 KB Output is correct
26 Correct 4 ms 312 KB Output is correct
27 Correct 5 ms 340 KB Output is correct
28 Correct 3 ms 212 KB Output is correct
29 Execution timed out 5052 ms 340 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 308 KB Output is correct
5 Correct 3 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 320 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 21 ms 340 KB Output is correct
17 Correct 3 ms 328 KB Output is correct
18 Correct 12 ms 352 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 11 ms 340 KB Output is correct
21 Correct 5 ms 340 KB Output is correct
22 Correct 8 ms 340 KB Output is correct
23 Correct 3 ms 308 KB Output is correct
24 Correct 2 ms 212 KB Output is correct
25 Correct 15 ms 212 KB Output is correct
26 Correct 4 ms 312 KB Output is correct
27 Correct 5 ms 340 KB Output is correct
28 Correct 3 ms 212 KB Output is correct
29 Execution timed out 5052 ms 340 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Execution timed out 5084 ms 396 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 15 ms 340 KB Output is correct
5 Correct 25 ms 312 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 19 ms 324 KB Output is correct
8 Execution timed out 5078 ms 212 KB Time limit exceeded
9 Halted 0 ms 0 KB -