| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 999410 |
2024-06-15T12:44:51 Z |
onbert |
Jail (JOI22_jail) |
C++17 |
|
18 ms |
98392 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 120005, maxN = 480005, lgn = 17, INF = 1e18;
int n, m;
vector<int> ADJ[maxn], adj[maxn];
pair<int,int> a[maxn];
int sz[maxn], d[maxn], newid[maxn], lim[maxn], cnter = 0;
void dfs1(int u) {
sz[u] = 1;
int fa = -1;
for (int &v:ADJ[u]) {
if (sz[v]) {
fa = v;
continue;
}
dfs1(v);
sz[u] += sz[v];
}
if (fa!=-1) ADJ[u].erase(find(ADJ[u].begin(), ADJ[u].end(), fa));
for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], adj[u][j]);
}
void dfs2(int u) {
cnter++;
newid[u] = cnter;
for (int v:ADJ[u]) dfs2(v);
lim[u] = cnter;
}
pair<int, vector<pair<int,int>>> binlift[maxn][lgn];
void dfs3(int u) {
for (int i=1;i<lgn;i++) {
if (binlift[u][i-1].first==-1 || binlift[binlift[u][i-1].first][i-1].first==-1) break;
binlift[u][i].first = binlift[binlift[u][i-1].first][i-1].first;
binlift[u][i].second = binlift[u][i-1].second;
for (auto [l, r]:binlift[binlift[u][i-1].first][i-1].second) {
if (r+1==binlift[u][i].second.back().first) binlift[u][i].second.back().first = l;
else binlift[u][i].second.push_back({l, r});
}
}
for (int v:adj[u]) {
d[v] = d[u] + 1;
binlift[v][0].first = u;
dfs3(v);
}
}
vector<pair<int,int>> path(int u, int v) {
vector<pair<int,int>> U, V;
if (d[u] > d[v]) swap(u, v);
for (int i=lgn-1;i>=0;i--) if (d[v] - (1<<i) >= d[u]) {
for (auto [l, r]:binlift[v][i].second) {
if (V.size()>0 && r+1==V.back().first) V.back().first = l;
else V.push_back({l, r});
// cout << l << " " << r << endl;
}
v = binlift[v][i].first;
}
if (u==v) return V;
for (int i=lgn-1;i>=0;i--) if (binlift[u][i].first != binlift[v][i].first) {
for (auto [l, r]:binlift[u][i].second) {
if (U.size()>0 && r+1==U.back().first) U.back().first = l;
else U.push_back({l, r});
}
u = binlift[u][i].first;
for (auto [l, r]:binlift[v][i].second) {
if (V.size()>0 && r+1==V.back().first) V.back().first = l;
else V.push_back({l, r});
}
v = binlift[v][i].first;
}
int fa = binlift[v][0].first;
if (U.size()>0 && u+1==U.back().first) U.back().first = u;
else U.push_back({u, u});
if (V.size()>0 && v+1==V.back().first) V.back().first = v;
else V.push_back({v, v});
if (V.size()>0 && fa+1==V.back().first) V.back().first = fa;
else V.push_back({fa, fa});
// cout << "U" << endl;
// for (auto [l, r]:U) cout << l << " " << r << endl;
// cout << "V" << endl;
// for (auto [l, r]:V) cout << l << " " << r << endl;
// cout << endl;
for (auto [l, r]:U) V.push_back({l, r});
return V;
}
struct node {
int val, lpt, rpt;
};
vector<node> seg[maxN][2];
void build(int id, int l, int r, int j) {
seg[id][j] = {{INF, 0, 0}};
if (l==r) return;
int mid = (l+r)/2;
build(id*2, l, mid, j);
build(id*2+1, mid+1, r, j);
}
void update(int id, int l, int r, int target, int val, int j) {
if (r<target || target<l) return;
if (l==r) {
seg[id][j].push_back({val, -1, -1});
return;
}
int mid = (l+r)/2;
update(id*2, l, mid, target, val, j);
update(id*2+1, mid+1, r, target, val, j);
seg[id][j].push_back({min(seg[id*2][j].back().val, seg[id*2+1][j].back().val), (int)seg[id*2][j].size()-1, (int)seg[id*2+1][j].size()-1});
}
int qry(int id, int pt, int l, int r, int findl, int findr, int j) {
if (r<findl || findr<l) return INF;
if (findl<=l && r<=findr) return seg[id][j][pt].val;
int mid = (l+r)/2;
int lhs = qry(id*2, seg[id][j][pt].lpt, l, mid, findl, findr, j);
int rhs = qry(id*2+1, seg[id][j][pt].rpt, mid+1, r, findl, findr, j);
return min(lhs, rhs);
}
int lb(int l, int r, int x, int j) {
// cout << l << " " << r << " " << x << " " << j << endl;
// cout << qry(1, n-x+1, 1, n, l, r, j) << endl;
return qry(1, n-x+1, 1, n, l, r, j);
}
void solve() {
cin >> n;
cnter = 0;
for (int i=1;i<=n;i++) sz[i] = 0, adj[i].clear(), ADJ[i].clear();
for (int i=1;i<=n-1;i++) {
int u, v;
cin >> u >> v;
ADJ[u].push_back(v);
ADJ[v].push_back(u);
}
dfs1(1); dfs2(1);
for (int u=1;u<=n;u++) for (int v:ADJ[u]) {
adj[newid[u]].push_back(newid[v]);
}
for (int i=1;i<=n;i++) for (int j=0;j<lgn;j++) binlift[i][j] = {-1, {{i, i}}};
dfs3(1);
// for (int i=1;i<=n;i++) {
// cout << "node " << i << endl;
// for (int j=0;j<lgn;j++) {
// if (binlift[i][j].first==-1) break;
// cout << binlift[i][j].first << " ";
// }
// cout << endl;
// }
cin >> m;
int S[n+1], T[n+1];
for (int i=0;i<=n;i++) S[i] = T[i] = 0;
a[0] = {1, INF};
for (int i=1;i<=m;i++) {
int s, t;
cin >> s >> t;
s = newid[s], t = newid[t];
a[i] = {s, t};
S[s] = i, T[t] = i;
}
build(1, 1, n, 0); build(1, 1, n, 1);
for (int i=n;i>=1;i--) {
if (T[i]==0) seg[1][0].push_back(seg[1][0].back());
else update(1, 1, n, a[T[i]].first, i, 0);
if (S[i]==0) seg[1][1].push_back(seg[1][1].back());
else update(1, 1, n, a[S[i]].second, i, 1);
// if (T[i]!=0) cout << 0 << " " << a[T[i]].first << " " << i << endl;
// if (S[i]!=0) cout << 1 << " " << a[S[i]].second << " " << i << endl;
}
for (int i=1;i<=m;i++) {
auto [s, t] = a[i];
vector<pair<int,int>> cur = path(s, t);
bool no = false;
vector<pair<int,int>> Schild = {{s+1, lim[s]}}, Tchild = {{t+1, lim[t]}};
if (s <= t && t <= lim[s]) {
int l;
if (adj[s].back() <= t) l = adj[s].back();
else l = adj[s][upper_bound(adj[s].begin(), adj[s].end(), t)-adj[s].begin()-1];
int r = lim[l];
Schild = {{1, s-1}, {s+1, l-1}, {r+1, n}};
} else if (t <= s && s <= lim[t]) {
int l;
if (adj[t].back() <= s) l = adj[t].back();
else l = adj[t][upper_bound(adj[t].begin(), adj[t].end(), s)-adj[t].begin()-1];
int r = lim[l];
Tchild = {{1, t-1}, {t+1, l-1}, {r+1, n}};
}
// cout << "S\n";
// for (auto [l, r]:Schild) cout << l << " " << r << endl;
// cout << "T\n";
// for (auto [l, r]:Tchild) cout << l << " " << r << endl;
for (auto [l, r]:cur) {
// cout << "range " << l << " " << r << endl;
for (auto [L, R]:Schild) no |= (lb(l, r, L, 0) <= R);
for (auto [L, R]:Tchild) no |= (lb(l, r, L, 1) <= R);
}
for (auto [sl, sr]:Schild) for (auto[tl, tr]:Tchild) {
no |= (lb(sl, sr, tl, 0) <= tr);
no |= (lb(sl, sr, tl, 1) <= tr);
}
if (no) {cout << "No\n"; return;}
}
cout << "Yes\n";
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
Compilation message
jail.cpp: In function 'void dfs1(long long int)':
jail.cpp:22:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
22 | for (int j=1;j<ADJ[u].size();j++) if (sz[ADJ[u][j]] > sz[ADJ[u][0]]) swap(ADJ[u][0], adj[u][j]);
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
98136 KB |
Output is correct |
| 2 |
Correct |
16 ms |
98136 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
98136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
98392 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
98140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
98392 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
98140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
98392 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
98140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
98392 KB |
Output is correct |
| 2 |
Incorrect |
16 ms |
98140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
98140 KB |
Output is correct |
| 2 |
Incorrect |
17 ms |
98140 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
98136 KB |
Output is correct |
| 2 |
Correct |
16 ms |
98136 KB |
Output is correct |
| 3 |
Incorrect |
16 ms |
98136 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
