oj.uz

Submission #891848

# Submission time Handle Problem Language Result Execution time Memory
891848 2023-12-24T08:37:09 Z aliarapov Jail (JOI22_jail) C++17
5 / 100
 3331 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[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 8 ms 52060 KB Output is correct
2 Correct 14 ms 52116 KB Output is correct
3 Correct 7 ms 52060 KB Output is correct
4 Correct 1503 ms 52116 KB Output is correct
5 Correct 3331 ms 52108 KB Output is correct
6 Correct 72 ms 52060 KB Output is correct
7 Correct 68 ms 52060 KB Output is correct
8 Correct 70 ms 52060 KB Output is correct
9 Correct 116 ms 52572 KB Output is correct
10 Correct 45 ms 65104 KB Output is correct
11 Correct 3242 ms 52096 KB Output is correct
12 Correct 3261 ms 52384 KB Output is correct
13 Correct 291 ms 65872 KB Output is correct
14 Correct 141 ms 66052 KB Output is correct
15 Correct 239 ms 66052 KB Output is correct
16 Correct 485 ms 67144 KB Output is correct
17 Correct 333 ms 66204 KB Output is correct
18 Correct 487 ms 67148 KB Output is correct
19 Correct 332 ms 66216 KB Output is correct
20 Correct 216 ms 66068 KB Output is correct
21 Correct 168 ms 66132 KB Output is correct
22 Correct 139 ms 66192 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 52104 KB Output is correct
3 Correct 71 ms 52124 KB Output is correct
4 Incorrect 68 ms 52124 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 52104 KB Output is correct
3 Correct 71 ms 52124 KB Output is correct
4 Incorrect 68 ms 52124 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 52104 KB Output is correct
3 Correct 71 ms 52124 KB Output is correct
4 Incorrect 68 ms 52124 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 52104 KB Output is correct
3 Correct 71 ms 52124 KB Output is correct
4 Incorrect 68 ms 52124 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 52060 KB Output is correct
2 Correct 11 ms 52116 KB Output is correct
3 Correct 16 ms 52060 KB Output is correct
4 Correct 7 ms 52060 KB Output is correct
5 Correct 3212 ms 52104 KB Output is correct
6 Incorrect 70 ms 52116 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 52060 KB Output is correct
2 Correct 14 ms 52116 KB Output is correct
3 Correct 7 ms 52060 KB Output is correct
4 Correct 1503 ms 52116 KB Output is correct
5 Correct 3331 ms 52108 KB Output is correct
6 Correct 72 ms 52060 KB Output is correct
7 Correct 68 ms 52060 KB Output is correct
8 Correct 70 ms 52060 KB Output is correct
9 Correct 116 ms 52572 KB Output is correct
10 Correct 45 ms 65104 KB Output is correct
11 Correct 3242 ms 52096 KB Output is correct
12 Correct 3261 ms 52384 KB Output is correct
13 Correct 291 ms 65872 KB Output is correct
14 Correct 141 ms 66052 KB Output is correct
15 Correct 239 ms 66052 KB Output is correct
16 Correct 485 ms 67144 KB Output is correct
17 Correct 333 ms 66204 KB Output is correct
18 Correct 487 ms 67148 KB Output is correct
19 Correct 332 ms 66216 KB Output is correct
20 Correct 216 ms 66068 KB Output is correct
21 Correct 168 ms 66132 KB Output is correct
22 Correct 139 ms 66192 KB Output is correct
23 Correct 8 ms 52060 KB Output is correct
24 Correct 8 ms 52104 KB Output is correct
25 Correct 71 ms 52124 KB Output is correct
26 Incorrect 68 ms 52124 KB Output isn't correct
27 Halted 0 ms 0 KB -