oj.uz

Submission #891852

# Submission time Handle Problem Language Result Execution time Memory
891852 2023-12-24T08:45:25 Z aliarapov Jail (JOI22_jail) C++17
61 / 100
 5000 ms 48720 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 sz[N], d[N], h[N], up[20][N];
int top[N], chain[N], tin[N], tout[N], rt, timer;

void clean(){
	d[1] = 0;
	for(int i = 1; i < N; i++){
		g[i].clear();
		for(int j = 0; j < 20; j++) up[j][i] = 0;
	}
}

struct SegmentTree{
	int tree[N * 4];
	int lazy[N * 4];

	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] = 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 0;
		if (l <= tl && tr <= r)return tree[v];
		int tm = (tl + tr) / 2;
		return 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;
	}
};

SegmentTree seg;

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;
    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);
        u = up[0][nxt];
    }
    seg.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);
}

void solve(){
	int n; 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;
    seg.clean();
    for(int i = 0; i < N; i++) top[i] = -1, h[i] = -1;
    rt = 0; timer = 0;
    dfs(1,1); HLD(1,1);
    
    for(auto [u,v] : qr) update(u,v,1);
    
	vector<int> cnt(m);
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			if(i == j) continue;
			auto [u,v] = qr[i];
			int goal = qr[j].ff;
			int lc = lca(u,v);
			if(((tin[goal] <= tin[u] && tout[u] <= tout[goal]) || 
				(tin[goal] <= tin[v] && tout[v] <= tout[goal])) && 
				(tin[lc] <= tin[goal] && tout[goal] <= tout[lc])) cnt[i]++;
		}
	}
    
    vector<int> vis(m);
    for(int time = 0; time < m; time++){
		bool ok = 0;
		int ind = 0;
		for(int i = 0; i < m; i++){
			if(vis[i]) continue;
			auto [u,v] = qr[i];
			update(u,v,-1);
			if(cnt[i] == 0 && seg.get(1,1,N,tin[v],tin[v]) == 0){
				vis[i] = 1;
				ok = 1;
				ind = i;
				break;
			}else{
				update(u,v,1);
			}
		}
		if(!ok){
			cout << "No\n";
			clean();
			return;
		}
		for(int i = 0; i < m; i++){
			auto [u,v] = qr[i];
			int goal = qr[ind].ff;
			int lc = lca(u,v);
			if(((tin[goal] <= tin[u] && tout[u] <= tout[goal]) || 
				(tin[goal] <= tin[v] && tout[v] <= tout[goal])) && 
				(tin[lc] <= tin[goal] && tout[goal] <= tout[lc])) cnt[i]--;
		}
	}
	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:215:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  215 | main(){
      | ^~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35932 KB Output is correct
2 Correct 12 ms 35932 KB Output is correct
3 Correct 8 ms 35932 KB Output is correct
4 Correct 1299 ms 36136 KB Output is correct
5 Correct 2683 ms 36144 KB Output is correct
6 Correct 59 ms 35932 KB Output is correct
7 Correct 66 ms 36164 KB Output is correct
8 Correct 81 ms 36160 KB Output is correct
9 Correct 596 ms 36704 KB Output is correct
10 Correct 193 ms 47416 KB Output is correct
11 Correct 2696 ms 36388 KB Output is correct
12 Correct 2955 ms 36424 KB Output is correct
13 Execution timed out 5053 ms 48392 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35932 KB Output is correct
2 Correct 7 ms 35928 KB Output is correct
3 Correct 58 ms 36172 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 62 ms 36188 KB Output is correct
6 Correct 57 ms 36184 KB Output is correct
7 Correct 58 ms 36180 KB Output is correct
8 Correct 56 ms 36184 KB Output is correct
9 Correct 59 ms 36436 KB Output is correct
10 Correct 58 ms 36176 KB Output is correct
11 Correct 54 ms 36188 KB Output is correct
12 Correct 56 ms 35932 KB Output is correct
13 Correct 57 ms 35932 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35932 KB Output is correct
2 Correct 7 ms 35928 KB Output is correct
3 Correct 58 ms 36172 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 62 ms 36188 KB Output is correct
6 Correct 57 ms 36184 KB Output is correct
7 Correct 58 ms 36180 KB Output is correct
8 Correct 56 ms 36184 KB Output is correct
9 Correct 59 ms 36436 KB Output is correct
10 Correct 58 ms 36176 KB Output is correct
11 Correct 54 ms 36188 KB Output is correct
12 Correct 56 ms 35932 KB Output is correct
13 Correct 57 ms 35932 KB Output is correct
14 Correct 9 ms 35928 KB Output is correct
15 Correct 12 ms 35932 KB Output is correct
16 Correct 58 ms 36164 KB Output is correct
17 Correct 57 ms 36188 KB Output is correct
18 Correct 57 ms 36188 KB Output is correct
19 Correct 57 ms 36136 KB Output is correct
20 Correct 58 ms 36188 KB Output is correct
21 Correct 57 ms 36188 KB Output is correct
22 Correct 58 ms 36184 KB Output is correct
23 Correct 56 ms 35932 KB Output is correct
24 Correct 61 ms 35932 KB Output is correct
25 Correct 58 ms 36188 KB Output is correct
26 Correct 56 ms 35928 KB Output is correct
27 Correct 58 ms 36184 KB Output is correct
28 Correct 56 ms 36136 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35932 KB Output is correct
2 Correct 7 ms 35928 KB Output is correct
3 Correct 58 ms 36172 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 62 ms 36188 KB Output is correct
6 Correct 57 ms 36184 KB Output is correct
7 Correct 58 ms 36180 KB Output is correct
8 Correct 56 ms 36184 KB Output is correct
9 Correct 59 ms 36436 KB Output is correct
10 Correct 58 ms 36176 KB Output is correct
11 Correct 54 ms 36188 KB Output is correct
12 Correct 56 ms 35932 KB Output is correct
13 Correct 57 ms 35932 KB Output is correct
14 Correct 9 ms 35928 KB Output is correct
15 Correct 12 ms 35932 KB Output is correct
16 Correct 58 ms 36164 KB Output is correct
17 Correct 57 ms 36188 KB Output is correct
18 Correct 57 ms 36188 KB Output is correct
19 Correct 57 ms 36136 KB Output is correct
20 Correct 58 ms 36188 KB Output is correct
21 Correct 57 ms 36188 KB Output is correct
22 Correct 58 ms 36184 KB Output is correct
23 Correct 56 ms 35932 KB Output is correct
24 Correct 61 ms 35932 KB Output is correct
25 Correct 58 ms 36188 KB Output is correct
26 Correct 56 ms 35928 KB Output is correct
27 Correct 58 ms 36184 KB Output is correct
28 Correct 56 ms 36136 KB Output is correct
29 Correct 78 ms 36184 KB Output is correct
30 Correct 68 ms 36208 KB Output is correct
31 Correct 62 ms 36208 KB Output is correct
32 Correct 73 ms 36188 KB Output is correct
33 Correct 59 ms 36188 KB Output is correct
34 Correct 64 ms 36188 KB Output is correct
35 Correct 70 ms 36440 KB Output is correct
36 Correct 103 ms 36192 KB Output is correct
37 Correct 94 ms 36176 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35932 KB Output is correct
2 Correct 7 ms 35928 KB Output is correct
3 Correct 58 ms 36172 KB Output is correct
4 Correct 57 ms 35928 KB Output is correct
5 Correct 62 ms 36188 KB Output is correct
6 Correct 57 ms 36184 KB Output is correct
7 Correct 58 ms 36180 KB Output is correct
8 Correct 56 ms 36184 KB Output is correct
9 Correct 59 ms 36436 KB Output is correct
10 Correct 58 ms 36176 KB Output is correct
11 Correct 54 ms 36188 KB Output is correct
12 Correct 56 ms 35932 KB Output is correct
13 Correct 57 ms 35932 KB Output is correct
14 Correct 9 ms 35928 KB Output is correct
15 Correct 12 ms 35932 KB Output is correct
16 Correct 58 ms 36164 KB Output is correct
17 Correct 57 ms 36188 KB Output is correct
18 Correct 57 ms 36188 KB Output is correct
19 Correct 57 ms 36136 KB Output is correct
20 Correct 58 ms 36188 KB Output is correct
21 Correct 57 ms 36188 KB Output is correct
22 Correct 58 ms 36184 KB Output is correct
23 Correct 56 ms 35932 KB Output is correct
24 Correct 61 ms 35932 KB Output is correct
25 Correct 58 ms 36188 KB Output is correct
26 Correct 56 ms 35928 KB Output is correct
27 Correct 58 ms 36184 KB Output is correct
28 Correct 56 ms 36136 KB Output is correct
29 Correct 78 ms 36184 KB Output is correct
30 Correct 68 ms 36208 KB Output is correct
31 Correct 62 ms 36208 KB Output is correct
32 Correct 73 ms 36188 KB Output is correct
33 Correct 59 ms 36188 KB Output is correct
34 Correct 64 ms 36188 KB Output is correct
35 Correct 70 ms 36440 KB Output is correct
36 Correct 103 ms 36192 KB Output is correct
37 Correct 94 ms 36176 KB Output is correct
38 Correct 611 ms 37716 KB Output is correct
39 Correct 203 ms 48720 KB Output is correct
40 Correct 1373 ms 37812 KB Output is correct
41 Correct 1512 ms 37652 KB Output is correct
42 Correct 997 ms 37900 KB Output is correct
43 Correct 88 ms 37980 KB Output is correct
44 Correct 153 ms 36432 KB Output is correct
45 Correct 211 ms 41820 KB Output is correct
46 Correct 199 ms 42044 KB Output is correct
47 Correct 53 ms 45404 KB Output is correct
48 Correct 58 ms 45500 KB Output is correct
49 Correct 240 ms 41844 KB Output is correct
50 Correct 236 ms 42056 KB Output is correct
51 Correct 46 ms 43092 KB Output is correct
52 Correct 48 ms 43092 KB Output is correct
53 Correct 773 ms 36816 KB Output is correct
54 Correct 107 ms 42580 KB Output is correct

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35928 KB Output is correct
2 Correct 9 ms 36148 KB Output is correct
3 Correct 12 ms 36132 KB Output is correct
4 Correct 6 ms 35932 KB Output is correct
5 Correct 2715 ms 36136 KB Output is correct
6 Correct 57 ms 35928 KB Output is correct
7 Correct 58 ms 35928 KB Output is correct
8 Correct 60 ms 36140 KB Output is correct
9 Correct 57 ms 35928 KB Output is correct
10 Correct 56 ms 35932 KB Output is correct
11 Correct 57 ms 35932 KB Output is correct
12 Correct 90 ms 36176 KB Output is correct
13 Correct 2771 ms 37052 KB Output is correct
14 Correct 2949 ms 37020 KB Output is correct
15 Correct 2806 ms 36948 KB Output is correct
16 Execution timed out 5064 ms 42324 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 35932 KB Output is correct
2 Correct 12 ms 35932 KB Output is correct
3 Correct 8 ms 35932 KB Output is correct
4 Correct 1299 ms 36136 KB Output is correct
5 Correct 2683 ms 36144 KB Output is correct
6 Correct 59 ms 35932 KB Output is correct
7 Correct 66 ms 36164 KB Output is correct
8 Correct 81 ms 36160 KB Output is correct
9 Correct 596 ms 36704 KB Output is correct
10 Correct 193 ms 47416 KB Output is correct
11 Correct 2696 ms 36388 KB Output is correct
12 Correct 2955 ms 36424 KB Output is correct
13 Execution timed out 5053 ms 48392 KB Time limit exceeded
14 Halted 0 ms 0 KB -