oj.uz

Submission #891914

# Submission time Handle Problem Language Result Execution time Memory
891914 2023-12-24T12:21:03 Z aliarapov Jail (JOI22_jail) C++17
5 / 100
 3474 ms 67148 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,1e18);
    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 i = 1; i <= n; i++) cout << seg.get(1,1,n,tin[i],tin[i]) << " \n"[i == n];
    //for(int i = 1; i <= n; i++) cout << T.get(1,1,n,tin[i],tin[i]) << " \n"[i == n];
    //for(int i = 1; i <= n; i++) cout << quer.get(1,1,n,tin[i],tin[i]) << " \n"[i == n];
    
    for(int time = 0; time < m; time++){
		if(T.tree[1] != 1){
			cout << "No\n";
			clean();
			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 << "No\n";
			clean();
			return;
		}
		T.update(tin[v],tin[v],1e18,1,1,n);
	}
	cout << "Yes\n";
    clean();
}
 
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
}

Compilation message

jail.cpp:261:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  261 | main(){
      | ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 14 ms 51892 KB Output is correct
3 Correct 9 ms 52048 KB Output is correct
4 Correct 1431 ms 52108 KB Output is correct
5 Correct 3074 ms 52364 KB Output is correct
6 Correct 66 ms 52060 KB Output is correct
7 Correct 66 ms 52060 KB Output is correct
8 Correct 75 ms 52056 KB Output is correct
9 Correct 115 ms 52572 KB Output is correct
10 Correct 44 ms 65108 KB Output is correct
11 Correct 3115 ms 52308 KB Output is correct
12 Correct 3474 ms 52148 KB Output is correct
13 Correct 327 ms 66044 KB Output is correct
14 Correct 161 ms 66056 KB Output is correct
15 Correct 276 ms 65820 KB Output is correct
16 Correct 683 ms 67148 KB Output is correct
17 Correct 362 ms 66212 KB Output is correct
18 Correct 493 ms 67144 KB Output is correct
19 Correct 339 ms 66208 KB Output is correct
20 Correct 235 ms 66212 KB Output is correct
21 Correct 181 ms 66208 KB Output is correct
22 Correct 162 ms 66212 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 72 ms 52056 KB Output is correct
4 Incorrect 68 ms 52116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 72 ms 52056 KB Output is correct
4 Incorrect 68 ms 52116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 72 ms 52056 KB Output is correct
4 Incorrect 68 ms 52116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 8 ms 52060 KB Output is correct
3 Correct 72 ms 52056 KB Output is correct
4 Incorrect 68 ms 52116 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 11 ms 52124 KB Output is correct
3 Correct 14 ms 52060 KB Output is correct
4 Correct 9 ms 52060 KB Output is correct
5 Correct 3158 ms 52108 KB Output is correct
6 Incorrect 69 ms 52060 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 52060 KB Output is correct
2 Correct 14 ms 51892 KB Output is correct
3 Correct 9 ms 52048 KB Output is correct
4 Correct 1431 ms 52108 KB Output is correct
5 Correct 3074 ms 52364 KB Output is correct
6 Correct 66 ms 52060 KB Output is correct
7 Correct 66 ms 52060 KB Output is correct
8 Correct 75 ms 52056 KB Output is correct
9 Correct 115 ms 52572 KB Output is correct
10 Correct 44 ms 65108 KB Output is correct
11 Correct 3115 ms 52308 KB Output is correct
12 Correct 3474 ms 52148 KB Output is correct
13 Correct 327 ms 66044 KB Output is correct
14 Correct 161 ms 66056 KB Output is correct
15 Correct 276 ms 65820 KB Output is correct
16 Correct 683 ms 67148 KB Output is correct
17 Correct 362 ms 66212 KB Output is correct
18 Correct 493 ms 67144 KB Output is correct
19 Correct 339 ms 66208 KB Output is correct
20 Correct 235 ms 66212 KB Output is correct
21 Correct 181 ms 66208 KB Output is correct
22 Correct 162 ms 66212 KB Output is correct
23 Correct 8 ms 52060 KB Output is correct
24 Correct 8 ms 52060 KB Output is correct
25 Correct 72 ms 52056 KB Output is correct
26 Incorrect 68 ms 52116 KB Output isn't correct
27 Halted 0 ms 0 KB -