| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 582741 | elkernos | Jail (JOI22_jail) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct digraph {
vector<vector<int>> g;
vector<int> deg;
digraph(int n) : g(n), deg(n) {}
void add(int a, int b)
{
g[a].push_back(b);
deg[b]++;
}
bool query(int n)
{
queue<int> q;
for(int i = 0; i < n; i++) {
if(deg[i] == 0) {
q.push(i);
}
}
while(!q.empty()) {
int x = q.front();
q.pop();
for(int y : g[x]) {
deg[y]--;
if(deg[y] == 0) {
q.push(y);
}
}
}
if(*max_element(deg.begin(), deg.begin() + n)) {
return 0;
}
return 1;
}
};
const int magic = 17;
void test_case()
{
int n;
cin >> n;
vector<vector<int>> g(n + 1);
for(int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<vector<int>> jump(magic, vector<int>(n + 1));
vector<int> dep(n + 1);
function<void(int, int)> dfs = [&](int u, int p) {
for(int to : g[u]) {
if(to == p) {
continue;
}
jump[0][to] = u;
dep[to] = dep[u] + 1;
dfs(to, u);
}
};
dfs(1, -1);
for(int i = 1; i < magic; i++) {
for(int j = 1; j <= n; j++) {
jump[i][j] = jump[i - 1][jump[i - 1][j]];
}
}
auto startIdx = [&](int i, int j) {
return (i + 1) * n + j - 1;
};
auto endIdx = [&](int i, int j) {
return (i + 18) * n + j - 1;
};
digraph dg(36 * n);
for(int i = 1; i < magic; i++) {
for(int j = 1; j <= n; j++) {
if(dep[j] + 1 >= (1 << i)) {
dg.add(startIdx(i, j), startIdx(i - 1, j));
dg.add(startIdx(i, j), startIdx(i - 1, jump[i - 1][j]));
dg.add(endIdx(i - 1, j), endIdx(i, j));
dg.add(endIdx(i - 1, jump[i - 1][j]), endIdx(i, j));
}
}
}
auto anc = [&](int a, int len) {
for(int i = 0; len > 0; i++) {
if(len % 2 == 1) {
a = jump[i][a];
}
len /= 2;
}
return a;
};
auto lca = [&](int a, int b) {
if(dep[a] > dep[b]) swap(a, b);
b = anc(b, dep[b] - dep[a]);
if(a == b) {
return a;
}
for(int i = magic - 1; i >= 0; i--) {
if(jump[i][a] != jump[i][b]) {
a = jump[i][a];
b = jump[i][b];
}
}
return jump[0][a];
};
int m;
cin >> m;
for(int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
dg.add(startIdx(0, a), i);
dg.add(i, endIdx(0, b));
int l = lca(a, b);
auto addEdge = [&](int v, int len) {
if(len <= 0) {
return;
}
int it = __lg(len);
int w = anc(v, len - (1 << it));
dg.add(i, startIdx(it, v));
dg.add(i, startIdx(it, w));
dg.add(endIdx(it, v), i);
dg.add(endIdx(it, w), i);
};
addEdge(jump[0][a], dep[a] - dep[l] - 1);
addEdge(jump[0][b], dep[b] - dep[l] - 1);
dg.add(endIdx(0, a), i);
dg.add(i, startIdx(0, b));
if(a != l) {
dg.add(i, startIdx(0, l));
}
if(b != l) {
dg.add(endIdx(0, l), i);
}
}
cout << (dg.query(36 * n) ? "Yes" : "No" << "\n";
}
int main()
{
cin.tie(nullptr)->sync_with_stdio(0);
int q;
cin >> q;
while(q--) {
test_case();
}
}