답안 #765157

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
765157	2023-06-24T08:52:34 Z	ymm	Jail (JOI22_jail)	C++17	21 / 100	90 ms	10068 KB

jail

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
vector<int> A[N];
vector<int> A0[N];
int st[N], ft[N];
int par[N];
int n, m;

void dfs(int v, int p, int &t)
{
	st[v] = t++;
	par[v] = p;
	for (int u : A0[v])
		if (u != p)
			dfs(u, v, t);
	ft[v] = t;
}

void add_edge(int i, int j)
{
	if (i == j)
		return;
	A[i].push_back(j);
}

vector<int> path(int i, int j)
{
	vector<int> ans;
	while (!(st[i] <= st[j] && st[j] < ft[i])) {
		ans.push_back(i);
		i = par[i];
	}
	ans.push_back(i);
	while (j != i) {
		ans.push_back(j);
		j = par[j];
	}
	return ans;
}

bool vis[N], anc[N];
bool dfs_cycle(int v)
{
	anc[v] = vis[v] = 1;
	for (int u : A[v]) {
		if (anc[u])
			return 1;
		if (vis[u])
			continue;
		if (dfs_cycle(u))
			return 1;
	}
	anc[v] = 0;
	return 0;
}

bool has_cycle()
{
	Loop (i,0,n)
		if (!vis[i] && dfs_cycle(i))
			return 1;
	return 0;
}

int s[N], t[N];
int sp[N], tp[N];

void traverse(int i)
{
	for (int u : path(s[i], t[i])) {
		if (sp[u] != -1)
			add_edge(sp[u], i);
		if (tp[u] != -1)
			add_edge(i, tp[u]);
	}
}

void init()
{
	cin >> n;
	memset(sp, -1, n*sizeof(*sp));
	memset(tp, -1, n*sizeof(*tp));
	memset(vis, 0, n*sizeof(*vis));
	memset(anc, 0, n*sizeof(*anc));
	Loop (i,0,n)
		A0[i].clear();
	Loop (i,1,n) {
		int v, u;
		cin >> v >> u;
		--v; --u;
		A0[v].push_back(u);
		A0[u].push_back(v);
	}
	cin >> m;
	Loop (i,0,m)
		A[i].clear();
	Loop (i,0,m) {
		cin >> s[i] >> t[i];
		--s[i]; --t[i];
		sp[s[i]] = i;
		tp[t[i]] = i;
	}
}

void solve()
{
	init();
	int dard = 0;
	dfs(0, -1, dard);
	Loop (i,0,m)
		traverse(i);
	cout << (has_cycle()? "No": "Yes") << '\n';
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int q;
	cin >> q;
	while (q--)
		solve();
}

Subtask #1
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	8 ms	5332 KB	Output is correct
5	Correct	15 ms	5692 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	4 ms	5204 KB	Output is correct
9	Correct	90 ms	8904 KB	Output is correct
10	Runtime error	6 ms	10068 KB	Execution killed with signal 6
11	Halted	0 ms	0 KB	-

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	5036 KB	Output is correct
4	Correct	3 ms	5040 KB	Output is correct
5	Correct	3 ms	5112 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	3 ms	5076 KB	Output is correct
9	Correct	3 ms	5076 KB	Output is correct
10	Correct	4 ms	5040 KB	Output is correct
11	Correct	3 ms	5036 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	2 ms	5076 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	5036 KB	Output is correct
4	Correct	3 ms	5040 KB	Output is correct
5	Correct	3 ms	5112 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	3 ms	5076 KB	Output is correct
9	Correct	3 ms	5076 KB	Output is correct
10	Correct	4 ms	5040 KB	Output is correct
11	Correct	3 ms	5036 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	2 ms	5076 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	2 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	3 ms	5036 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	3 ms	5076 KB	Output is correct
21	Correct	3 ms	5076 KB	Output is correct
22	Correct	4 ms	5076 KB	Output is correct
23	Correct	3 ms	5048 KB	Output is correct
24	Correct	3 ms	5076 KB	Output is correct
25	Correct	3 ms	5076 KB	Output is correct
26	Correct	2 ms	4992 KB	Output is correct
27	Correct	3 ms	5076 KB	Output is correct
28	Correct	2 ms	4948 KB	Output is correct

Subtask #4
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	5036 KB	Output is correct
4	Correct	3 ms	5040 KB	Output is correct
5	Correct	3 ms	5112 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	3 ms	5076 KB	Output is correct
9	Correct	3 ms	5076 KB	Output is correct
10	Correct	4 ms	5040 KB	Output is correct
11	Correct	3 ms	5036 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	2 ms	5076 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	2 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	3 ms	5036 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	3 ms	5076 KB	Output is correct
21	Correct	3 ms	5076 KB	Output is correct
22	Correct	4 ms	5076 KB	Output is correct
23	Correct	3 ms	5048 KB	Output is correct
24	Correct	3 ms	5076 KB	Output is correct
25	Correct	3 ms	5076 KB	Output is correct
26	Correct	2 ms	4992 KB	Output is correct
27	Correct	3 ms	5076 KB	Output is correct
28	Correct	2 ms	4948 KB	Output is correct
29	Correct	4 ms	5140 KB	Output is correct
30	Incorrect	3 ms	5044 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	2 ms	4948 KB	Output is correct
3	Correct	3 ms	5036 KB	Output is correct
4	Correct	3 ms	5040 KB	Output is correct
5	Correct	3 ms	5112 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	3 ms	5076 KB	Output is correct
9	Correct	3 ms	5076 KB	Output is correct
10	Correct	4 ms	5040 KB	Output is correct
11	Correct	3 ms	5036 KB	Output is correct
12	Correct	2 ms	5076 KB	Output is correct
13	Correct	2 ms	5076 KB	Output is correct
14	Correct	2 ms	4948 KB	Output is correct
15	Correct	2 ms	4948 KB	Output is correct
16	Correct	3 ms	5076 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	3 ms	5036 KB	Output is correct
19	Correct	2 ms	4948 KB	Output is correct
20	Correct	3 ms	5076 KB	Output is correct
21	Correct	3 ms	5076 KB	Output is correct
22	Correct	4 ms	5076 KB	Output is correct
23	Correct	3 ms	5048 KB	Output is correct
24	Correct	3 ms	5076 KB	Output is correct
25	Correct	3 ms	5076 KB	Output is correct
26	Correct	2 ms	4992 KB	Output is correct
27	Correct	3 ms	5076 KB	Output is correct
28	Correct	2 ms	4948 KB	Output is correct
29	Correct	4 ms	5140 KB	Output is correct
30	Incorrect	3 ms	5044 KB	Output isn't correct
31	Halted	0 ms	0 KB	-

Subtask #6
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	2 ms	5028 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Incorrect	8 ms	5216 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #7
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4948 KB	Output is correct
4	Correct	8 ms	5332 KB	Output is correct
5	Correct	15 ms	5692 KB	Output is correct
6	Correct	3 ms	5076 KB	Output is correct
7	Correct	3 ms	5076 KB	Output is correct
8	Correct	4 ms	5204 KB	Output is correct
9	Correct	90 ms	8904 KB	Output is correct
10	Runtime error	6 ms	10068 KB	Execution killed with signal 6
11	Halted	0 ms	0 KB	-

답안 #765157

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