oj.uz

Submission #660197

# Submission time Handle Problem Language Result Execution time Memory
660197 2022-11-21T05:50:30 Z Sohsoh84 Jail (JOI22_jail) C++17
5 / 100
 5000 ms 43852 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll LOG = 20;

int n, m, t, tin[MAXN], tout[MAXN], S[MAXN], T[MAXN], Par[MAXN][LOG];
vector<int> adj[MAXN];

void dfs(int v, int p) {
	tin[v] = ++t;
	Par[v][0] = p;

	for (int u : adj[v])
		if (u != p)
			dfs(u, v);

	tout[v] = t;
}

inline bool par(int u, int v) {
	return tin[u] <= tin[v] && tout[u] >= tout[v];
}

inline int LCA(int u, int v) {
	if (par(u, v)) return u;
	if (par(v, u)) return v;

	for (int i = LOG - 1; i >= 0; i--)
		if (Par[u][i] != 0 && !par(Par[u][i], v))
			u = Par[u][i];

	return Par[u][0];
}

inline bool in_path(int v, int a, int b) {
	int lca = LCA(a, b);
	if (!par(lca, v)) return false;
	return par(v, a) || par(v, b);
}

inline int solve() {
	t = 0;
	for (int i = 0; i < n + 10; i++) adj[i].clear();

	cin >> n;
	for (int i = 1; i < n; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	dfs(1, 0);
	for (int i = 1; i < LOG; i++)
		for (int v = 1; v <= n; v++)
			Par[v][i] = Par[Par[v][i - 1]][i - 1];

	cin >> m;
	bool flag = true;
	for (int i = 1; i <= m; i++) {
		cin >> S[i] >> T[i];
		for (int j = 1; j < i; j++) {
			flag &= (!(in_path(T[i], S[j], T[j]) && in_path(T[j], S[i], T[i])));
			flag &= (!(in_path(S[i], S[j], T[j]) && in_path(S[j], S[i], T[i])));
			flag &= (!(in_path(S[i], S[j], T[j]) && in_path(T[i], S[j], T[j])));
			flag &= (!(in_path(S[j], S[i], T[i]) && in_path(T[j], S[i], T[i])));
		}
	}

	return cout << (flag ? "Yes" : "No") << endl, 0;
	return 0;
}

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23792 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 19 ms 23764 KB Output is correct
5 Correct 32 ms 23872 KB Output is correct
6 Correct 12 ms 23880 KB Output is correct
7 Correct 13 ms 23848 KB Output is correct
8 Correct 14 ms 23884 KB Output is correct
9 Correct 75 ms 24784 KB Output is correct
10 Correct 57 ms 43528 KB Output is correct
11 Correct 15 ms 23764 KB Output is correct
12 Correct 56 ms 23860 KB Output is correct
13 Execution timed out 5074 ms 43852 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23788 KB Output is correct
7 Correct 13 ms 23824 KB Output is correct
8 Correct 13 ms 23824 KB Output is correct
9 Correct 13 ms 23916 KB Output is correct
10 Correct 13 ms 23820 KB Output is correct
11 Correct 14 ms 23828 KB Output is correct
12 Correct 14 ms 23820 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23788 KB Output is correct
7 Correct 13 ms 23824 KB Output is correct
8 Correct 13 ms 23824 KB Output is correct
9 Correct 13 ms 23916 KB Output is correct
10 Correct 13 ms 23820 KB Output is correct
11 Correct 14 ms 23828 KB Output is correct
12 Correct 14 ms 23820 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct
14 Incorrect 14 ms 23816 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23788 KB Output is correct
7 Correct 13 ms 23824 KB Output is correct
8 Correct 13 ms 23824 KB Output is correct
9 Correct 13 ms 23916 KB Output is correct
10 Correct 13 ms 23820 KB Output is correct
11 Correct 14 ms 23828 KB Output is correct
12 Correct 14 ms 23820 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct
14 Incorrect 14 ms 23816 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Correct 12 ms 23764 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23820 KB Output is correct
5 Correct 13 ms 23892 KB Output is correct
6 Correct 13 ms 23788 KB Output is correct
7 Correct 13 ms 23824 KB Output is correct
8 Correct 13 ms 23824 KB Output is correct
9 Correct 13 ms 23916 KB Output is correct
10 Correct 13 ms 23820 KB Output is correct
11 Correct 14 ms 23828 KB Output is correct
12 Correct 14 ms 23820 KB Output is correct
13 Correct 13 ms 23892 KB Output is correct
14 Incorrect 14 ms 23816 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23764 KB Output is correct
2 Incorrect 11 ms 23832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23792 KB Output is correct
2 Correct 12 ms 23816 KB Output is correct
3 Correct 12 ms 23744 KB Output is correct
4 Correct 19 ms 23764 KB Output is correct
5 Correct 32 ms 23872 KB Output is correct
6 Correct 12 ms 23880 KB Output is correct
7 Correct 13 ms 23848 KB Output is correct
8 Correct 14 ms 23884 KB Output is correct
9 Correct 75 ms 24784 KB Output is correct
10 Correct 57 ms 43528 KB Output is correct
11 Correct 15 ms 23764 KB Output is correct
12 Correct 56 ms 23860 KB Output is correct
13 Execution timed out 5074 ms 43852 KB Time limit exceeded
14 Halted 0 ms 0 KB -