# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
950663 |
2024-03-20T14:41:35 Z |
vladilius |
Jail (JOI22_jail) |
C++17 |
|
11 ms |
9512 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int msz = 2e5 + 5;
const int lg = 22;
struct Seg_Tree{
vector<int> t, p;
int n;
void init(int ns){
n = ns;
t.assign(4 * n, 0);
p.assign(4 * n, 0);
}
void push(int& v, int& vv){
if (!p[v]) return;
t[vv] += p[v]; t[vv + 1] += p[v];
p[vv] += p[v]; p[vv + 1] += p[v];
p[v] = 0;
}
void upd(int v, int tl, int tr, int& l, int& r, int& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
t[v] += x;
p[v] += x;
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv);
upd(vv, tl, tm, l, r, x);
upd(vv + 1, tm + 1, tr, l, r, x);
}
void upd(int& l, int& r, int x){
upd(1, 1, n, l, r, x);
}
int get(int v, int tl, int tr, int& l, int& r){
if (l > tr || r < tl) return 0;
if (l <= tl && tr <= r) return t[v];
int tm = (tl + tr) / 2, vv = 2 * v;
push(v, vv);
return get(vv, tl, tm, l, r) + get(vv + 1, tm + 1, tr, l, r);
}
int get(int& l, int& r){
return get(1, 1, n, l, r);
}
};
vector<int> g[msz], pw[lg], tin(msz), tout(msz), pp(msz);
int timer = 0;
void fill_dfs(int v, int pr){
pp[v] = pr;
tin[v] = ++timer;
pw[0][v] = pr;
for (int i = 1; i < lg; i++){
pw[i][v] = pw[i - 1][pw[i - 1][v]];
}
for (int i: g[v]){
if (i == pr) continue;
fill_dfs(i, v);
}
tout[v] = timer;
}
bool check(int u, int v){
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int u, int v){
if (check(u, v)) return u;
if (check(v, u)) return v;
for (int i = lg - 1; i >= 0; i--){
if (!check(pw[i][u], v)){
u = pw[i][u];
}
}
return pw[0][u]; // pp[u]
}
vector<int> p(msz);
vector<int> used(msz);
int get(int v){
if (used[v] || !v) return v;
if (p[v] == v){
p[v] = pp[p[v]];
}
return p[v] = get(p[v]);
}
vector<bool> vis(msz, false);
vector<int> order, w, h, l;
void dfs(int v){
used[w[v]] = 0;
int k;
while (check(l[v], k = get(pp[w[v]]))){
if (!k) break;
dfs(used[k]);
}
while (check(l[v], k = get(h[v]))){
if (!k) break;
dfs(used[k]);
}
order.push_back(v);
}
Seg_Tree T;
vector<bool> s(msz);
int sum(int& u, int& v, int& l){
return T.get(tin[u], tin[u]) + T.get(tin[v], tin[v]) - 2 * T.get(tin[l], tin[l]) + s[l];
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int q; cin>>q;
while (q--){
int n; cin>>n;
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i < n; i++){
int a, b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
int m; cin>>m;
w.resize(m + 1);
h.resize(m + 1);
used.assign(n + 1, 0);
for (int i = 1; i <= m; i++){
cin>>w[i]>>h[i];
used[w[i]] = i;
}
for (int i = 0; i < lg; i++){
pw[i].resize(n + 1);
}
fill_dfs(1, 1); pp[1] = 0;
l.resize(m + 1);
for (int i = 1; i <= m; i++){
l[i] = lca(w[i], h[i]);
}
for (int i = 1; i <= n; i++){
p[i] = i;
}
for (int i = 1; i <= m; i++){
if (!used[w[i]]) continue;
dfs(i);
}
T.init(n);
s.assign(n + 1, false);
for (int i = 1; i <= m; i++){
s[w[i]] = true;
T.upd(tin[w[i]], tout[w[i]], 1);
}
bool ind = true;
for (int i: order){
if (sum(w[i], h[i], l[i]) > 1){
ind = false;
break;
}
T.upd(tin[w[i]], tout[w[i]], -1);
s[w[i]] = false;
}
order.clear();
cout<<((ind) ? "Yes" : "No")<<"\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9052 KB |
Output is correct |
2 |
Correct |
3 ms |
9052 KB |
Output is correct |
3 |
Correct |
3 ms |
9052 KB |
Output is correct |
4 |
Incorrect |
11 ms |
9512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
8904 KB |
Output is correct |
3 |
Incorrect |
4 ms |
9052 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
8904 KB |
Output is correct |
3 |
Incorrect |
4 ms |
9052 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
8904 KB |
Output is correct |
3 |
Incorrect |
4 ms |
9052 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9048 KB |
Output is correct |
2 |
Correct |
3 ms |
8904 KB |
Output is correct |
3 |
Incorrect |
4 ms |
9052 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9048 KB |
Output is correct |
2 |
Incorrect |
3 ms |
9052 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
9052 KB |
Output is correct |
2 |
Correct |
3 ms |
9052 KB |
Output is correct |
3 |
Correct |
3 ms |
9052 KB |
Output is correct |
4 |
Incorrect |
11 ms |
9512 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |