| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 891913 |
2023-12-24T12:19:58 Z |
aliarapov |
Jail (JOI22_jail) |
C++17 |
|
66 ms |
52116 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define ordered_set tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset tree<type1, null_type, less_equal<type1>, rb_tree_tag, tree_order_statistics_node_update>;
using namespace std;
using namespace __gnu_pbds;
const int mod = 1e9+7;
const double PI = acos(-1.0);
const double epsilon = 1e-6;
const int N = 1.2e5+5;
vector<int> g[N];
int n;
int sz[N], d[N], h[N], up[20][N];
int top[N], chain[N], tin[N], tout[N], rt, timer, pos[N];
void clean(){
d[1] = 0;
for(int i = 0; i < N; i++){
pos[i] = 0;
g[i].clear();
for(int j = 0; j < 20; j++) up[j][i] = 0;
}
}
struct SegmentTree{
int tree[N * 4];
int lazy[N * 4];
function<int(int,int)> f;
int type;
SegmentTree(function<int(int,int)> func, int ty){
f = func;
type = ty;
}
void build(const vector<int> &a,int v, int l, int r){
if(l == r){
tree[v] = a[l];
return;
}
int mid = (l + r) >> 1;
build(a,v * 2, l, mid);
build(a,v * 2 + 1, mid + 1, r);
tree[v] = f(tree[v * 2], tree[v * 2 + 1]);
}
void push(int v, int tl, int tr) {
if (lazy[v] == 0) return;
if (tl != tr) {
lazy[v * 2] += lazy[v];
lazy[v * 2 + 1] += lazy[v];
}
tree[v] += lazy[v];
lazy[v] = 0;
}
void update(int l, int r, int x, int v, int tl, int tr) {
push(v, tl, tr);
if (l > tr || tl > r) return ;
if (l <= tl && tr <= r) {
lazy[v] = x;
push(v, tl, tr);
return;
}
int tm = (tl + tr) / 2;
update(l, r, x, v * 2, tl, tm);
update(l, r, x, v * 2 + 1, tm + 1, tr);
tree[v] = f(tree[v * 2], tree[v * 2 + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
push(v, tl, tr);
if (l > tr || tl > r) return type;
if (l <= tl && tr <= r) return tree[v];
int tm = (tl + tr) / 2;
return f(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}
void clean(){
for(int i = 0; i < N * 4; i++) tree[i] = 0,lazy[i] = 0;
}
int search(int v,int tl,int tr){
push(v, tl, tr);
if(tl == tr){
return pos[tl];
}
int tm = (tl + tr) / 2;
if(tree[v * 2] + lazy[v * 2] == tree[v]) return search(v*2,tl,tm);
else return search(v*2+1,tm+1,tr);
}
};
function<int(int,int)> minm = [](int a,int b){
return min(a,b);
};
function<int(int,int)> summ = [](int a,int b){
return a + b;
};
SegmentTree seg(summ,0),T(minm,1e18),quer(summ,0);
void dfs(int u, int p){
up[0][u] = p;
for ( int i = 1; i < 20; i++ ){
up[i][u] = up[i - 1][up[i - 1][u]];
}
sz[u] = 1;
for ( auto &v: g[u] ){
if ( v != p ){
d[v] = d[u] + 1;
dfs(v, u);
sz[u] += sz[v];
}
}
for ( auto &v: g[u] ){
if ( v != p ){
if ( h[u] == -1 || sz[h[u]] < sz[v] ){
h[u] = v;
}
}
}
}
int lca(int u, int v){
if ( d[u] < d[v] ) swap(u, v);
int df = d[u] - d[v];
for ( int i = 0; i < 20; i++ ){
if ( df >> i & 1 ){
u = up[i][u];
}
}
if ( u == v ){
return u;
}
for ( int i = 19; i >= 0; i-- ){
if ( up[i][u] != up[i][v] ){
u = up[i][u];
v = up[i][v];
}
}
return up[0][u];
};
void HLD(int u, int p){
tin[u] = ++timer;
pos[timer] = u;
chain[u] = rt;
if ( top[rt] == -1 ){
top[rt] = u;
}
if ( h[u] != -1 ) HLD(h[u], u);
for ( auto &v: g[u] ){
if ( v != p && h[u] != v ){
rt++; HLD(v, u);
}
}
tout[u] = timer;
}
void upd(int u,int v,int val){
if ( d[u] < d[v] ) swap(u, v);
while ( chain[u] != chain[v] ){
int nxt = top[chain[u]];
seg.update(tin[nxt],tin[u],val,1,1,n);
T.update(tin[nxt],tin[u],val,1,1,n);
u = up[0][nxt];
}
seg.update(tin[v],tin[u],val,1,1,n);
T.update(tin[v],tin[u],val,1,1,n);
}
void update(int u,int v, int val){
int lc = lca(u,v);
upd(u,lc,val); upd(v,lc,val);
seg.update(tin[lc],tin[lc],-val,1,1,n);
T.update(tin[lc],tin[lc],-val,1,1,n);
}
int qry(int u,int v){
if ( d[u] < d[v] ) swap(u, v);
int res = 0;
while ( chain[u] != chain[v] ){
int nxt = top[chain[u]];
res += quer.get(1,1,n,tin[nxt],tin[u]);
u = up[0][nxt];
}
res += quer.get(1,1,n,tin[v],tin[u]);
return res;
}
int query(int u,int v){
int lc = lca(u,v);
return qry(u,lc) + qry(v,lc);
}
void solve(){
cin >> n;
for(int i = 1; i < n; i++){
int u,v; cin >> u >> v;
g[u].pb(v); g[v].pb(u);
}
int m; cin >> m;
vector<pair<int,int> > qr(m);
for(auto &[l,r] : qr) cin >> l >> r;
quer.clean();
seg.clean();
T.clean();
for(int i = 0; i < N; i++) top[i] = -1, h[i] = -1;
rt = 0; timer = 0;
dfs(1,1); HLD(1,1);
vector<int> vec(n+1);
for(int i = 0; i < m; i++) vec[qr[i].ss] = i;
vector<int> A(n+1,1e9);
for(auto [u,v] : qr) A[tin[v]] = 0;
T.build(A,1,1,n);
for(auto [u,v] : qr) quer.update(tin[u],tin[u],1,1,1,n);
for(auto [u,v] : qr) update(u,v,1);
for(int time = 0; time < m; time++){
if(T.tree[1] != 1){
cout << "No\n";
return;
}
int i = vec[T.search(1,1,n)];
auto [u,v] = qr[i];
update(u,v,-1);
quer.update(tin[u],tin[u],-1,1,1,n);
if(!(query(u,v) == 0 && seg.get(1,1,n,tin[v],tin[v]) == 0)){
cout << query(u,v) << ' ' << seg.get(1,1,n,tin[v],tin[v]) << "No\n";
return;
}
T.update(tin[v],tin[v],1e9,1,1,n);
}
cout << "Yes\n";
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int tt = 1;
cin >> tt;
while (tt--) {
solve();
clean();
}
}
/*
1
8
1 2
2 3
2 4
3 5
3 6
3 7
7 8
4
1 5
4 6
7 3
8 7
*/
Compilation message
jail.cpp:257:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
257 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
52116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52048 KB |
Output is correct |
| 3 |
Incorrect |
66 ms |
52060 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52048 KB |
Output is correct |
| 3 |
Incorrect |
66 ms |
52060 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52048 KB |
Output is correct |
| 3 |
Incorrect |
66 ms |
52060 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52048 KB |
Output is correct |
| 3 |
Incorrect |
66 ms |
52060 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
10 ms |
52068 KB |
Output is correct |
| 3 |
Incorrect |
14 ms |
52060 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
52116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
