oj.uz

Submission #891223

# Submission time Handle Problem Language Result Execution time Memory
891223 2023-12-22T14:01:59 Z vjudge1 Jail (JOI22_jail) C++17
61 / 100
 5000 ms 50252 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 9 ms 35928 KB Output is correct
2 Correct 12 ms 36152 KB Output is correct
3 Correct 6 ms 35928 KB Output is correct
4 Correct 1229 ms 36508 KB Output is correct
5 Correct 2639 ms 36892 KB Output is correct
6 Correct 57 ms 36188 KB Output is correct
7 Correct 59 ms 36188 KB Output is correct
8 Correct 77 ms 36184 KB Output is correct
9 Correct 614 ms 37712 KB Output is correct
10 Correct 199 ms 48744 KB Output is correct
11 Correct 2699 ms 36288 KB Output is correct
12 Correct 2854 ms 37172 KB Output is correct
13 Execution timed out 5043 ms 50252 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35932 KB Output is correct
2 Correct 6 ms 35932 KB Output is correct
3 Correct 58 ms 36188 KB Output is correct
4 Correct 57 ms 36188 KB Output is correct
5 Correct 56 ms 36172 KB Output is correct
6 Correct 61 ms 36188 KB Output is correct
7 Correct 58 ms 36184 KB Output is correct
8 Correct 57 ms 36188 KB Output is correct
9 Correct 58 ms 36184 KB Output is correct
10 Correct 58 ms 36184 KB Output is correct
11 Correct 49 ms 36188 KB Output is correct
12 Correct 59 ms 36160 KB Output is correct
13 Correct 57 ms 35928 KB Output is correct
14 Correct 9 ms 35932 KB Output is correct
15 Correct 12 ms 35932 KB Output is correct
16 Correct 58 ms 36200 KB Output is correct
17 Correct 61 ms 36184 KB Output is correct
18 Correct 59 ms 36192 KB Output is correct
19 Correct 64 ms 36196 KB Output is correct
20 Correct 57 ms 36184 KB Output is correct
21 Correct 57 ms 36188 KB Output is correct
22 Correct 70 ms 36188 KB Output is correct
23 Correct 58 ms 35932 KB Output is correct
24 Correct 57 ms 35932 KB Output is correct
25 Correct 61 ms 36184 KB Output is correct
26 Correct 57 ms 35932 KB Output is correct
27 Correct 59 ms 36188 KB Output is correct
28 Correct 58 ms 35928 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35932 KB Output is correct
2 Correct 6 ms 35932 KB Output is correct
3 Correct 58 ms 36188 KB Output is correct
4 Correct 57 ms 36188 KB Output is correct
5 Correct 56 ms 36172 KB Output is correct
6 Correct 61 ms 36188 KB Output is correct
7 Correct 58 ms 36184 KB Output is correct
8 Correct 57 ms 36188 KB Output is correct
9 Correct 58 ms 36184 KB Output is correct
10 Correct 58 ms 36184 KB Output is correct
11 Correct 49 ms 36188 KB Output is correct
12 Correct 59 ms 36160 KB Output is correct
13 Correct 57 ms 35928 KB Output is correct
14 Correct 9 ms 35932 KB Output is correct
15 Correct 12 ms 35932 KB Output is correct
16 Correct 58 ms 36200 KB Output is correct
17 Correct 61 ms 36184 KB Output is correct
18 Correct 59 ms 36192 KB Output is correct
19 Correct 64 ms 36196 KB Output is correct
20 Correct 57 ms 36184 KB Output is correct
21 Correct 57 ms 36188 KB Output is correct
22 Correct 70 ms 36188 KB Output is correct
23 Correct 58 ms 35932 KB Output is correct
24 Correct 57 ms 35932 KB Output is correct
25 Correct 61 ms 36184 KB Output is correct
26 Correct 57 ms 35932 KB Output is correct
27 Correct 59 ms 36188 KB Output is correct
28 Correct 58 ms 35928 KB Output is correct
29 Correct 76 ms 36184 KB Output is correct
30 Correct 68 ms 36216 KB Output is correct
31 Correct 63 ms 36184 KB Output is correct
32 Correct 69 ms 36188 KB Output is correct
33 Correct 58 ms 36188 KB Output is correct
34 Correct 64 ms 36188 KB Output is correct
35 Correct 72 ms 36192 KB Output is correct
36 Correct 95 ms 36200 KB Output is correct
37 Correct 98 ms 35932 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 35932 KB Output is correct
2 Correct 6 ms 35932 KB Output is correct
3 Correct 58 ms 36188 KB Output is correct
4 Correct 57 ms 36188 KB Output is correct
5 Correct 56 ms 36172 KB Output is correct
6 Correct 61 ms 36188 KB Output is correct
7 Correct 58 ms 36184 KB Output is correct
8 Correct 57 ms 36188 KB Output is correct
9 Correct 58 ms 36184 KB Output is correct
10 Correct 58 ms 36184 KB Output is correct
11 Correct 49 ms 36188 KB Output is correct
12 Correct 59 ms 36160 KB Output is correct
13 Correct 57 ms 35928 KB Output is correct
14 Correct 9 ms 35932 KB Output is correct
15 Correct 12 ms 35932 KB Output is correct
16 Correct 58 ms 36200 KB Output is correct
17 Correct 61 ms 36184 KB Output is correct
18 Correct 59 ms 36192 KB Output is correct
19 Correct 64 ms 36196 KB Output is correct
20 Correct 57 ms 36184 KB Output is correct
21 Correct 57 ms 36188 KB Output is correct
22 Correct 70 ms 36188 KB Output is correct
23 Correct 58 ms 35932 KB Output is correct
24 Correct 57 ms 35932 KB Output is correct
25 Correct 61 ms 36184 KB Output is correct
26 Correct 57 ms 35932 KB Output is correct
27 Correct 59 ms 36188 KB Output is correct
28 Correct 58 ms 35928 KB Output is correct
29 Correct 76 ms 36184 KB Output is correct
30 Correct 68 ms 36216 KB Output is correct
31 Correct 63 ms 36184 KB Output is correct
32 Correct 69 ms 36188 KB Output is correct
33 Correct 58 ms 36188 KB Output is correct
34 Correct 64 ms 36188 KB Output is correct
35 Correct 72 ms 36192 KB Output is correct
36 Correct 95 ms 36200 KB Output is correct
37 Correct 98 ms 35932 KB Output is correct
38 Correct 589 ms 37712 KB Output is correct
39 Correct 197 ms 48848 KB Output is correct
40 Correct 1313 ms 38328 KB Output is correct
41 Correct 1530 ms 37864 KB Output is correct
42 Correct 999 ms 37980 KB Output is correct
43 Correct 89 ms 38228 KB Output is correct
44 Correct 153 ms 36432 KB Output is correct
45 Correct 207 ms 41892 KB Output is correct
46 Correct 199 ms 41808 KB Output is correct
47 Correct 55 ms 45404 KB Output is correct
48 Correct 56 ms 45576 KB Output is correct
49 Correct 241 ms 41820 KB Output is correct
50 Correct 243 ms 42064 KB Output is correct
51 Correct 49 ms 42908 KB Output is correct
52 Correct 48 ms 43100 KB Output is correct
53 Correct 777 ms 36952 KB Output is correct
54 Correct 105 ms 42576 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 35932 KB Output is correct
3 Correct 12 ms 36160 KB Output is correct
4 Correct 6 ms 35932 KB Output is correct
5 Correct 2723 ms 36432 KB Output is correct
6 Correct 61 ms 35932 KB Output is correct
7 Correct 57 ms 35928 KB Output is correct
8 Correct 62 ms 36128 KB Output is correct
9 Correct 57 ms 35928 KB Output is correct
10 Correct 59 ms 35932 KB Output is correct
11 Correct 59 ms 35932 KB Output is correct
12 Correct 89 ms 36444 KB Output is correct
13 Correct 2841 ms 36512 KB Output is correct
14 Correct 2963 ms 37408 KB Output is correct
15 Correct 2813 ms 36864 KB Output is correct
16 Execution timed out 5029 ms 42488 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 35928 KB Output is correct
2 Correct 12 ms 36152 KB Output is correct
3 Correct 6 ms 35928 KB Output is correct
4 Correct 1229 ms 36508 KB Output is correct
5 Correct 2639 ms 36892 KB Output is correct
6 Correct 57 ms 36188 KB Output is correct
7 Correct 59 ms 36188 KB Output is correct
8 Correct 77 ms 36184 KB Output is correct
9 Correct 614 ms 37712 KB Output is correct
10 Correct 199 ms 48744 KB Output is correct
11 Correct 2699 ms 36288 KB Output is correct
12 Correct 2854 ms 37172 KB Output is correct
13 Execution timed out 5043 ms 50252 KB Time limit exceeded
14 Halted 0 ms 0 KB -