답안 #552221

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552221	2022-04-22T19:16:05 Z	LucaDantas	Jail (JOI22_jail)	C++17	21 / 100	5000 ms	396 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #552221

Compilation message

Subtask #1 0 / 5.0

Subtask #2 5.0 / 5.0

Subtask #3 16.0 / 16.0

Subtask #4 0 / 28.0

Subtask #5 0 / 12.0

Subtask #6 0 / 11.0

Subtask #7 0 / 23.0

Subtask #1
0 / 5.0

Subtask #2
5.0 / 5.0

Subtask #3
16.0 / 16.0

Subtask #4
0 / 28.0

Subtask #5
0 / 12.0

Subtask #6
0 / 11.0

Subtask #7
0 / 23.0