| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 848722 |
2023-09-13T11:17:39 Z |
danikoynov |
Jail (JOI22_jail) |
C++14 |
|
35 ms |
123508 KB |
/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 2e5 + 10;
int n, m, s[maxn], t[maxn], parent[maxn];
vector < int > adj[maxn], children[maxn];
void input()
{
cin >> n;
for (int i = 1; i < n; i ++)
{
int a, b;
cin >> a >> b;
adj[a].push_back(b);
adj[b].push_back(a);
}
cin >> m;
for (int i = 1; i <= m; i ++)
{
cin >> s[i] >> t[i];
}
}
int tin[maxn], tout[maxn], occ[2 * maxn], depth[maxn], timer;
int sub[maxn], heavy[maxn];
void euler(int v = 1, int p = -1)
{
tin[v] = ++ timer;
occ[timer] = v;
sub[v] = 1;
heavy[v] = -1;
parent[v] = p;
for (int u : adj[v])
{
if (u == p)
continue;
children[v].push_back(u);
depth[u] = depth[v] + 1;
euler(u, v);
if (heavy[v] == -1 || sub[u] > sub[heavy[v]])
heavy[v] = u;
sub[v] += sub[u];
occ[++ timer] = v;
}
tout[v] = timer;
}
const int maxlog = 20;
int dp[maxlog][maxn * 2], lg[2 * maxn];
void build_sparse_table()
{
for (int i = 1; i <= timer; i ++)
{
dp[0][i] = occ[i];
lg[i] = lg[i / 2] + 1;
}
for (int j = 1; j < lg[timer]; j ++)
{
for (int i = 1; i <= timer - (1 << j) + 1; i ++)
{
dp[j][i] = dp[j - 1][i + (1 << (j - 1))];
if (depth[dp[j - 1][i]] < depth[dp[j][i]])
dp[j][i] = dp[j - 1][i];
}
}
}
int get_lca(int v, int u)
{
int l = tin[v], r = tin[u];
if (l > r)
swap(l, r);
int len = lg[r - l + 1] - 1;
int lca = dp[len][r - (1 << len) + 1];
if (depth[dp[len][l]] < depth[lca])
lca = dp[len][l];
return lca;
}
vector < int > graph[10 * maxn];
bool is_cycle;
bool in_subtree(int v, int u)
{
return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
bool on_path(int v, int u, int w)
{
int lca = get_lca(v, u);
if (in_subtree(lca, w) && in_subtree(w, v))
return true;
if (in_subtree(lca, w) && in_subtree(w, u))
return true;
return false;
}
void check_prisoners(int i, int j)
{
/**if (on_path(s[i], t[i], s[j]) && on_path(s[i], t[i], t[j]))
{
is_cycle = true;
return;
}*/
if (on_path(s[i], t[i], s[j]))
{
graph[i].push_back(j);
return;
}
if (on_path(s[i], t[i], t[j]))
{
graph[j].push_back(i);
return;
}
}
vector < pair < int, int > > link[maxn];
set < pair < int, int > > loc_set[maxn];
bool cmp(pair < int, int > di, pair < int, int > dj)
{
int i = di.second, j = dj.second;
int d1 = depth[s[i]] + depth[t[i]] - 2 * depth[get_lca(s[i], t[i])];
int d2 = depth[s[j]] + depth[t[j]] - 2 * depth[get_lca(s[j], t[j])];
return d1 > d2;
}
bool check_range(int idx, int left, int right)
{
pair < int, int > cur = {left, -1};
set < pair < int, int > > :: iterator it = loc_set[idx].lower_bound(cur);
if (it == loc_set[idx].end())
return false;
if (it -> first <= right)
return true;
return false;
}
int find_child(int v, int u)
{
int lf = 0, rf = (int)(children[v].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (tout[children[v][mf]] < tin[u])
lf = mf + 1;
else
rf = mf - 1;
}
return children[v][lf];
}
void dfs(int v, int p)
{
for (int u : adj[v])
{
if (u == p)
continue;
dfs(u, v);
if (loc_set[u].size() > loc_set[v].size())
swap(loc_set[u], loc_set[v]);
for (pair < int, int > cur : loc_set[u])
{
pair < int, int > par = {tin[s[cur.second]], cur.second};
if (tin[s[cur.second]] == cur.first)
par.first = tin[t[cur.second]];
if (loc_set[v].find(par) != loc_set[v].end())
loc_set[v].erase(par);
else
loc_set[v].insert(cur);
}
}
sort(link[v].begin(), link[v].end(), cmp);
for (pair < int, int > cur : link[v])
{
pair < int, int > par = {tin[s[cur.second]], cur.second};
if (tin[s[cur.second]] == cur.first)
par.first = tin[t[cur.second]];
///cout << "here " << cur.first << " " << cur.second << " " << par.first << " " << par.second << " " << tin[s[cur.second]] << endl;
if (loc_set[v].find(par) != loc_set[v].end())
{
loc_set[v].erase(par);
continue;
}
int idx = cur.second, u = s[idx];
if (u == v)
u = t[idx];
if (!in_subtree(u, v))
{
if (check_range(v, tin[u], tout[u]))
is_cycle = true;
}
else
{
int child = find_child(u, v);
///cout << "HERE " << child << " " << u << endl;
if (check_range(v, 1, tin[child] - 1) || check_range(v, tout[child] + 1, timer))
{
///cout << "FOUND CYCLE " << v << " " << u << " " << child << endl;
is_cycle = true;
}
}
loc_set[v].insert(cur);
}
/**cout << v << " : " << p << endl;
for (pair < int, int > cur : loc_set[v])
cout << cur.first << " " << cur.second << endl;
cout << "cycle " << is_cycle << endl;
cout << "-------------" << endl;*/
}
struct chain
{
int top, left, right;
} ch[maxn];
int ord[maxn], ch_idx[maxn], ch_cnt, to, ch_pos[maxn];
void hld(int v)
{
ch_idx[v] = ch_cnt;
ord[++ to] = v;
ch[ch_idx[v]].right = to;
ch_pos[v] = to;
if (heavy[v] != -1)
hld(heavy[v]);
for (int u : children[v])
{
if (u == heavy[v])
continue;
ch_cnt ++;
ch[ch_cnt].top = v;
ch[ch_cnt].left = to + 1;
ch[ch_cnt].right = to;
hld(u);
}
}
vector < int > ver_start[maxn], ver_end[maxn]; /// might be replaced
void add_edge(int v, int u)
{
graph[v].push_back(u);
///cout << v << " " << u << endl;
}
void build_forward_tree(int root, int left, int right)
{
///cout << root + m << " : " << left << " " << right << endl;
if (left == right)
{
for (int v : ver_start[left])
add_edge(root + m, v);
///graph[root + m].push_back(v);
return;
}
int mid = (left + right) / 2;
add_edge(root + m, root * 2 + m);
add_edge(root + m, root * 2 + 1 + m);
///graph[root + m].push_back(root * 2 + m);
///graph[root + m].push_back(root * 2 + 1 + m);
build_forward_tree(root * 2, left, mid);
build_forward_tree(root * 2 + 1, mid + 1, right);
}
vector < int > bkt[maxn * 4];
void build_backward_tree(int root, int left, int right)
{
bkt[root].clear();
if (left == right)
{
for (int v : ver_end[left])
{
bkt[root].push_back(v);
add_edge(v, root + m + 4 * n);
///graph[v].push_back(root + m + 4 * n);
///cout << v << " here " << left << endl;
}
return;
}
int mid = (left + right) / 2;
///add_edge(root * 2 + m + 4 * n, root + m + 4 * n);
///add_edge(root * 2 + 1 + m + 4 * n, root + m + 4 * n);
///graph[root * 2 + m + 4 * n].push_back(root + m + 4 * n);
///graph[root * 2 + 1 + m + 4 * n].push_back(root + m + 4 * n);
build_backward_tree(root * 2, left, mid);
build_backward_tree(root * 2 + 1, mid + 1, right);
for (int v : bkt[root * 2])
bkt[root].push_back(v);
for (int v : bkt[root * 2 + 1])
bkt[root].push_back(v);
for (int v : bkt[root])
add_edge(v, root + m + 4 * n);
}
void add_forward(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
add_edge(val, root + m);
///graph[val].push_back(root + m);
return;
}
int mid = (left + right) / 2;
add_forward(root * 2, left, mid, qleft, qright, val);
add_forward(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
void add_backward(int root, int left, int right, int qleft, int qright, int val)
{
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
add_edge(root + m + 4 * n, val);
///graph[root + m + 4 * n].push_back(val);
return;
}
int mid = (left + right) / 2;
add_backward(root * 2, left, mid, qleft, qright, val);
add_backward(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
void add_path_forward(int v, int lca, int idx)
{
while(ch_idx[v] != ch_idx[lca])
{
add_forward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
///add_backward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
v = ch[ch_idx[v]].top;
}
///cout << "idx " << idx << " " << ch_pos[lca] << " " << ch_pos[v] << endl;
add_forward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
///add_backward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
}
void add_path_backward(int v, int lca, int idx)
{
while(ch_idx[v] != ch_idx[lca])
{
///add_forward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
add_backward(1, 1, n, ch[ch_idx[v]].left, ch_pos[v], idx);
v = ch[ch_idx[v]].top;
}
///cout << "idx " << idx << " " << ch_pos[lca] << " " << ch_pos[v] << endl;
///add_forward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
add_backward(1, 1, n, ch_pos[lca], ch_pos[v], idx);
}
void build_graph()
{
for (int i = 1; i <= m; i ++)
{
link[s[i]].push_back({tin[t[i]], i});
link[t[i]].push_back({tin[s[i]], i});
ver_start[s[i]].push_back(i);
ver_end[t[i]].push_back(i);
}
ch_cnt = 0;
to = 0;
ch[++ ch_cnt].top = 0;
ch[ch_cnt].left = 1;
ch[ch_cnt].right = 0;
hld(1);
build_backward_tree(1, 1, n);
build_forward_tree(1, 1, n);
for (int i = 1; i <= m; i ++)
{
int lca = get_lca(s[i], t[i]);
if (depth[s[i]] + depth[t[i]] - 2 * depth[lca] != 1)
{
int v = s[i], u = t[i];
if (lca != v && lca != u)
{
v = parent[v];
u = parent[u];
}
else if (lca == v)
{
v = find_child(v, u);
u = parent[u];
}
else if (lca == u)
{
u = find_child(u, v);
v = parent[v];
}
lca = get_lca(v, u);
///cout << "path " << v << " : " << u << endl;
add_path_forward(v, lca, i);
add_path_forward(u, lca, i);
add_path_backward(v, lca, i);
add_path_backward(u, lca, i);
}
for (pair < int, int > cur : link[s[i]])
{
if (i != cur.second)
check_prisoners(i, cur.second);
}
}
/**for (int i = 1; i <= m; i ++)
{
for (int j = 1; j <= m; j ++)
{
if (i != j)
check_prisoners(i, j);
}
}*/
}
int used[maxn];
void check_dag(int v)
{
used[v] = 1;
for (int u : graph[v])
{
if (used[u] == 2)
continue;
///cout << v << " : " << u << endl;
if (used[u] == 1)
is_cycle = 1;
else
{
check_dag(u);
}
}
used[v] = 2;
}
void check_graph()
{
for (int i = 1; i <= m + 8 * n; i ++)
{
if (!used[i])
check_dag(i);
}
if (is_cycle)
cout << "No" << endl;
else
cout << "Yes" << endl;
}
void clear_data()
{
is_cycle = false;
for (int i = 1; i <= m + 8 * n; i ++)
graph[i].clear(), used[i] = 0;
for (int i = 1; i <= n; i ++)
{
adj[i].clear();
link[i].clear();
ver_start[i].clear();
ver_end[i].clear();
children[i].clear();
loc_set[i].clear();
}
timer = 0;
}
void solve()
{
input();
euler();
build_sparse_table();
build_graph();
check_graph();
clear_data();
}
int main()
{
speed();
///freopen("test.txt", "r", stdin);
int q;
cin >> q;
while(q --)
solve();
return 0;
}
/**
1
7
1 2
2 3
3 4
4 5
3 6
6 7
2
4 1
5 7
1
4
1 2
2 3
3 4
2
1 3
2 4
1
5
1 2
1 3
2 4
2 5
1
4 5
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
117424 KB |
Output is correct |
| 2 |
Correct |
23 ms |
117340 KB |
Output is correct |
| 3 |
Correct |
23 ms |
113240 KB |
Output is correct |
| 4 |
Incorrect |
35 ms |
123484 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
117340 KB |
Output is correct |
| 2 |
Correct |
23 ms |
113496 KB |
Output is correct |
| 3 |
Correct |
26 ms |
123484 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
123508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
117340 KB |
Output is correct |
| 2 |
Correct |
23 ms |
113496 KB |
Output is correct |
| 3 |
Correct |
26 ms |
123484 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
123508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
117340 KB |
Output is correct |
| 2 |
Correct |
23 ms |
113496 KB |
Output is correct |
| 3 |
Correct |
26 ms |
123484 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
123508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
117340 KB |
Output is correct |
| 2 |
Correct |
23 ms |
113496 KB |
Output is correct |
| 3 |
Correct |
26 ms |
123484 KB |
Output is correct |
| 4 |
Incorrect |
27 ms |
123508 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
117336 KB |
Output is correct |
| 2 |
Correct |
23 ms |
117340 KB |
Output is correct |
| 3 |
Correct |
23 ms |
117340 KB |
Output is correct |
| 4 |
Correct |
23 ms |
113240 KB |
Output is correct |
| 5 |
Incorrect |
30 ms |
119388 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
117424 KB |
Output is correct |
| 2 |
Correct |
23 ms |
117340 KB |
Output is correct |
| 3 |
Correct |
23 ms |
113240 KB |
Output is correct |
| 4 |
Incorrect |
35 ms |
123484 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
