oj.uz

Submission #765157

# Submission time Handle Problem Language Result Execution time Memory
765157 2023-06-24T08:52:34 Z ymm Jail (JOI22_jail) C++17
21 / 100
 90 ms 10068 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -