| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 848689 |
2023-09-13T09:48:32 Z |
danikoynov |
Jail (JOI22_jail) |
C++14 |
|
7 ms |
35164 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];
vector < int > adj[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;
void euler(int v = 1, int p = -1)
{
tin[v] = ++ timer;
occ[timer] = v;
for (int u : adj[v])
{
if (u == p)
continue;
depth[u] = depth[v] + 1;
euler(u, v);
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[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)(adj[v].size()) - 1;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (tout[mf] < tin[u])
lf = mf + 1;
else
rf = mf - 1;
}
return adj[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]] == par.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]] == par.first)
par.first = tin[t[cur.second]];
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(v, u);
if (check_range(v, 1, tin[child] - 1) || check_range(v, tout[child] + 1, timer))
is_cycle = true;
}
loc_set[v].insert(cur);
}
///cout << v << " : " << p << endl;
}
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});
}
dfs(1, -1);
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; 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; i ++)
graph[i].clear(), used[i] = 0;
for (int i = 1; i <= n; i ++)
{
adj[i].clear();
link[i].clear();
loc_set[i].clear();
}
timer = 0;
}
void solve()
{
input();
euler();
build_sparse_table();
build_graph();
check_graph();
clear_data();
}
int main()
{
speed();
int q;
cin >> q;
while(q --)
solve();
return 0;
}
/**
1
4
1 2
2 3
3 4
2
1 4
3 2
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
35164 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
35160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
