| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 702947 |
2023-02-25T11:16:38 Z |
piOOE |
Jail (JOI22_jail) |
C++17 |
|
3 ms |
3164 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class HLD {
public:
vector<int> par, siz, head, tin, tout, ord, depth;
int dfs1(int i, vector<vector<int>> &g) {
for (int &t: g[i]) {
if (t != par[i]) {
depth[t] = depth[i] + 1;
par[t] = i;
siz[i] += dfs1(t, g);
if (siz[t] > siz[g[i][0]] || g[i][0] == par[i]) swap(t, g[i][0]);
}
}
return siz[i];
}
void dfs2(int i, int &T, const vector<vector<int>> &g) {
tin[i] = T++;
for (int t: g[i]) {
if (t != par[i]) {
head[t] = (T == tin[i] + 1 ? head[i] : t);
dfs2(t, T, g);
}
}
tout[i] = T;
}
HLD(vector<vector<int>> g, int r = 0)
: par(g.size(), -1), siz(g.size(), 1), head(g.size(), r), tin(g.size()), ord(g.size()), tout(g.size()),
depth(g.size()){
dfs1(r, g);
int x = 0;
dfs2(r, x, g);
for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
}
vector<pair<int, int>> path(int a, int b) {
vector<pair<int, int>> res;
for (;; b = par[head[b]]) {
if (tin[b] < tin[a]) swap(a, b);
if (tin[head[b]] <= tin[a]) {
res.emplace_back(tin[a], tin[b] + 1);
return res;
}
res.emplace_back(tin[head[b]], tin[b] + 1);
}
}
pair<int, int> subtree(int i) {
return {tin[i], tin[i] + siz[i]};
}
int dist(int a, int b) {
return depth[a] + depth[b] - 2 * depth[lca(a, b)];
}
int lca(int a, int b) {
for (;; b = par[head[b]]) {
if (tin[b] < tin[a]) swap(a, b);
if (tin[head[b]] <= tin[a]) return a;
}
}
bool isp(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
};
constexpr int N = 1.2e5, D = 256 * 1024;
constexpr int N_ = D + N * 18 * 2;
vector<int> g[N];
int top = 0;
int used[N], in[D], out[D];
int sz = 1;
void init(int n) {
sz = 1 << __lg(n) + !!(n & (n - 1));
for (int i = sz + n - 1; i > 0; --i) {
in[i] = top++;
out[i] = top++;
}
}
void solve() {
int n;
cin >> n;
vector<vector<int>> adj(n);
for (int i = 1; i < n; ++i) {
int a, b;
cin >> a >> b;
a -= 1, b -= 1;
adj[a].push_back(b);
adj[b].push_back(a);
}
HLD tree(adj);
int m;
cin >> m;
top = m;
init(n);
vector<array<int, 2>> prisoner(m);
for (auto &[s, t] : prisoner) {
cin >> s >> t;
s -= 1, t -= 1;
}
for (int i = 0; i < m; ++i) {
auto [S, T] = prisoner[i];
for (int x = S + sz; x > 0; x >>= 1) {
g[in[x]].push_back(i);
g[in[x]].push_back(top);
in[x] = top++;
}
for (int x = T + sz; x > 0; x >>= 1) {
g[i].push_back(out[x]);
g[top].push_back(out[x]);
out[x] = top++;
}
auto path = tree.path(S, T);
for (auto [lx, rx] : path) {
for (lx += sz, rx += sz; lx < rx; lx >>= 1, rx >>= 1) {
if (lx & 1) {
g[i].push_back(in[lx]);
g[out[lx]].push_back(i);
lx++;
}
if (rx & 1) {
rx -= 1;
g[i].push_back(in[rx]);
g[out[rx]].push_back(i);
}
}
}
}
bool yay = true;
memset(used, 0, sizeof(used[0]) * top);
auto dfs = [&](auto self, int v) -> void {
used[v] = 1;
for (int to : g[v]) {
if (!used[to]) {
self(self, to);
} else if (used[to] == 1) {
yay = false;
}
}
used[v] = 2;
};
for (int i = 0; i < m; ++i) {
if (!used[i]) {
dfs(dfs, i);
}
}
for (int i = 0; i < top; ++i) {
g[i].clear();
}
cout << (yay ? "Yes\n" : "No\n");
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test = 1;
cin >> test;
while (test--) {
solve();
}
return 0;
}
Compilation message
jail.cpp: In constructor 'HLD::HLD(std::vector<std::vector<int> >, int)':
jail.cpp:8:44: warning: 'HLD::ord' will be initialized after [-Wreorder]
8 | vector<int> par, siz, head, tin, tout, ord, depth;
| ^~~
jail.cpp:8:38: warning: 'std::vector<int> HLD::tout' [-Wreorder]
8 | vector<int> par, siz, head, tin, tout, ord, depth;
| ^~~~
jail.cpp:33:5: warning: when initialized here [-Wreorder]
33 | HLD(vector<vector<int>> g, int r = 0)
| ^~~
jail.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for (int i = 0; i < g.size(); ++i) ord[tin[i]] = i;
| ~~^~~~~~~~~~
jail.cpp: In function 'void init(int)':
jail.cpp:84:23: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
84 | sz = 1 << __lg(n) + !!(n & (n - 1));
| ~~~~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3080 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3080 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3080 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3080 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
3164 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3148 KB |
Output is correct |
| 2 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
3156 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
3156 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
