oj.uz

Submission #814978

# Submission time Handle Problem Language Result Execution time Memory
814978 2023-08-08T11:30:49 Z WonderfulWhale Jail (JOI22_jail) C++17
72 / 100
 5000 ms 878220 KB 
//#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define int int64_t
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
 
int Gg = 0;
 
struct SegTree {
	int T=1;
	vector<unordered_set<int>> t;
	void build(int n) {
		T=1;
		while(T<=n) T*=2;
		t.resize(2*T);
		for(int i=0;i<2*T;i++) t[i].clear();
	}
	vector<int> query(int l, int r) {
		l+=T, r+=T;
		vector<int> ret;
		for(int x:t[l]) ret.pb(x);
		if(l!=r) for(int x:t[r]) ret.pb(x);
		while(l/2!=r/2) {
			if(l%2==0) for(int x:t[l+1]) ret.pb(x);
			if(r%2==1) for(int x:t[r-1]) ret.pb(x);
			l/=2;
			r/=2;
		}
		return ret;
	}
	void add(int x, int val) {
		x+=T;
		while(x) {
			t[x].insert(val);
			x/=2;
		}
	}
	void remove(int x, int val) {
		x+=T;
		while(x) {
			t[x].erase(val);
			x/=2;
		}
	}
};
struct SegTree2 {
	int T = 1;
	vector<unordered_set<int>> t;
	void build(int n) {
		T=1;
		while(T<=n) T*=2;
		t.resize(2*T);
		for(int i=0;i<2*T;i++) t[i].clear();
	}
	void add(int l, int r, int val) {
		l+=T, r+=T;
		t[l].insert(val);
		if(l!=r) t[r].insert(val);
		while(l/2!=r/2) {
			if(l%2==0) t[l+1].insert(val);
			if(r%2==1) t[r-1].insert(val);
			l/=2;
			r/=2;
		}
	}
	void remove(int l, int r, int val) {
		l+=T, r+=T;
		t[l].erase(val);
		if(l!=r) t[r].insert(val);
		while(l/2!=r/2) {
			if(l%2==0) t[l+1].erase(val);
			if(r%2==1) t[r-1].erase(val);
			l/=2;
			r/=2;
		}
	}
	vector<int> query(int x) {
		vector<int> ret;
		x+=T;
		while(x) {
			for(int y:t[x]) ret.pb(y);
			x/=2;
		}
		return ret;
	}
};
 
vector<int> G[120009];
vector<int> G2[120009];
int tin[120009], tout[120009], T;
int jp2[120009][20];
int deg[120009];
pii tab[120009];
int col[120009];
int dep[120009];
int p[120009];
int heavy[120009];
int pos[120009], P;
int head[120009];
 
 
int dfs(int x, int y) {
	p[x] = y;
	dep[x] = dep[y]+1;
	int sz = 1, max_sz=0;
	tin[x] = ++T;
	jp2[x][0] = y;
	for(int i=1;i<20;i++) jp2[x][i] = jp2[jp2[x][i-1]][i-1];
	for(int z:G[x]) if(z!=y) {
		int c_sz = dfs(z, x);
		sz += c_sz;
		if(c_sz>max_sz) {
			max_sz = c_sz;
			heavy[x] = z;
		} 
	}
	tout[x] = ++T;
	return sz;
}
 
void decompose(int x, int h) {
	head[x] = h;
	pos[x] = ++P;
	if(heavy[x]) {
		decompose(heavy[x], h);
	}
	for(int y:G[x]) {
		if(y!=p[x]&&y!=heavy[x]) decompose(y, y);
	}
}
 
bool is_ancestor(int x, int y) {
    	return tin[x]<=tin[y]&&tout[x]>=tout[y];
    }
     
    int lca(int x, int y) {
    	if(is_ancestor(x, y)) return x;
    	if(is_ancestor(y, x)) return y;
    	for(int i=19;i>=0;i--) {
    		if(!is_ancestor(jp2[x][i], y)) {
    			x = jp2[x][i];
    		}
    	}
    	return jp2[x][0];
    }
     
    bool is_on_path(int x, int a, int b) {
    	return is_ancestor(a, x)&&is_ancestor(x, b);
    }
     
    bool f(int x, int a, int b) {
    	int y = lca(a, b);
    	//cerr << "lca: " << a << " " << b << " " << y << "\n";
    	//cerr << "checking: " << x << " " << a << " " << b << " " << (is_on_path(x, y, a)||is_on_path(x, y, b)) << "\n";
    	return is_on_path(x, y, a)||is_on_path(x, y, b);
    }
     
    SegTree seg1;
    SegTree2 seg2;
     
    vector<int> hld_query(int a, int b) {
    	//cout << "hld_query: " << a << " " << b << "\n";
    	vector<int> ret;
    	for (; head[a] != head[b]; b=p[head[b]]) {
    		if (dep[head[a]] > dep[head[b]]) swap(a, b);
    		for(int x:seg1.query(pos[head[b]], pos[b])) ret.pb(x);
    	}
    	if (dep[a] > dep[b]) swap(a, b);
    	for(int x:seg1.query(pos[a], pos[b])) ret.pb(x);
    	return ret;
    }
     
    void hld_add(int a, int b, int val) {
    	//cout << "hld_query: " << a << " " << b << "\n";
    	vector<int> ret;
    	for (; head[a] != head[b]; b=p[head[b]]) {
    		if (dep[head[a]] > dep[head[b]]) swap(a, b);
    		seg2.add(pos[head[b]], pos[b], val);
    	}
    	if (dep[a] > dep[b]) swap(a, b);
    	seg2.add(pos[a], pos[b], val);
    }
     
    void hld_remove(int a, int b, int val) {
    	//cout << "hld_query: " << a << " " << b << "\n";
    	vector<int> ret;
    	for (; head[a] != head[b]; b=p[head[b]]) {
    		if (dep[head[a]] > dep[head[b]]) swap(a, b);
    		seg2.remove(pos[head[b]], pos[b], val);
    	}
    	if (dep[a] > dep[b]) swap(a, b);
    	seg2.remove(pos[a], pos[b], val);
    }
     
    int N;
     
    bool dfs2(int x) {
    	assert(col[x]==0);
    	col[x] = 1;
    	vector<int> v1 = hld_query(tab[x].st, tab[x].nd);
    	Gg += sz(v1);
    	//assert(Gg<=2*N);
    	for(int y:v1){ 
    		if(y==x) continue;
    		if(col[y]==1) return false;
    	}
    	for(int y:v1) {
    		if(y==x) continue;
    		if(col[y]==1) return false;
    		if(col[y]==0&&!dfs2(y)) return false;
    	}
    	vector<int> v2 = seg2.query(pos[tab[x].nd]);
    	Gg += sz(v2);
    	//assert(Gg<=2*N);
    	for(int y:v2) {
    		if(y==x) continue;
    		if(col[y]==1) return false;
    	}
    	for(int y:v2) {
    		if(y==x) continue;
    		if(col[y]==1) return false;
    		if(col[y]==0&&!dfs2(y)) return false;
    	}
    	col[x] = 2;
    	seg1.remove(pos[tab[x].st], x);
    	hld_remove(tab[x].st, tab[x].nd, x);
    	return true;
    }
     
    int32_t main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
     
    	int q=1;
    	cin >> q;
    	while(q--) {
    		int n, m;
    		cin >> n;
    		N = n;
    		Gg=0;
    		for(int i=1;i<=n;i++) {
    			G[i].clear();
    			head[i] = 0;
    			heavy[i] = 0;
    			dep[i] = 0;
    			p[i] = 0;
    		}
    		for(int i=0;i<n-1;i++) {
    			int a, b;
    			cin >> a >> b;
    			G[a].pb(b);
    			G[b].pb(a);
    		}
    		tin[0] = T = 0;
    		dfs(1, 0);
    		P = 0;
    		decompose(1, 1);
    		tout[0] = T;
    		cin >> m;
    		for(int i=0;i<m;i++) {
    			G2[i].clear();
    			deg[i] = 0;
    			col[i] = 0;
    		}
    		seg1.build(n+9);
    		seg2.build(n+9);
    		for(int i=0;i<m;i++) {
    			cin >> tab[i].st >> tab[i].nd;
    			seg1.add(pos[tab[i].st], i);
    			hld_add(tab[i].st, tab[i].nd, i);
    		}
    		bool ans = true;
    		for(int i=0;i<m;i++) {
				if(!ans) continue;
    			if(!col[i]) {
    				ans&=dfs2(i);
    			}
    		}
    		if(ans) {
    			cout << "Yes\n";
    		} else {
    			cout << "No\n";
    		}
    	}
    }

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6016 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 2 ms 5972 KB Output is correct
4 Correct 15 ms 6172 KB Output is correct
5 Correct 31 ms 6176 KB Output is correct
6 Correct 4 ms 6256 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 6 ms 6356 KB Output is correct
9 Correct 50 ms 12688 KB Output is correct
10 Correct 76 ms 74332 KB Output is correct
11 Correct 10 ms 5972 KB Output is correct
12 Correct 53 ms 6188 KB Output is correct
13 Correct 354 ms 162360 KB Output is correct
14 Correct 397 ms 167424 KB Output is correct
15 Correct 1000 ms 176696 KB Output is correct
16 Correct 2867 ms 294400 KB Output is correct
17 Correct 501 ms 201676 KB Output is correct
18 Correct 574 ms 224804 KB Output is correct
19 Correct 467 ms 191564 KB Output is correct
20 Correct 593 ms 189844 KB Output is correct
21 Execution timed out 5078 ms 878220 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 6 ms 6228 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 5 ms 6228 KB Output is correct
8 Correct 6 ms 6188 KB Output is correct
9 Correct 6 ms 6228 KB Output is correct
10 Correct 4 ms 6232 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 3 ms 6100 KB Output is correct
13 Correct 3 ms 6100 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 6 ms 6228 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 5 ms 6228 KB Output is correct
8 Correct 6 ms 6188 KB Output is correct
9 Correct 6 ms 6228 KB Output is correct
10 Correct 4 ms 6232 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 3 ms 6100 KB Output is correct
13 Correct 3 ms 6100 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 4 ms 6228 KB Output is correct
17 Correct 4 ms 6228 KB Output is correct
18 Correct 4 ms 6228 KB Output is correct
19 Correct 3 ms 5972 KB Output is correct
20 Correct 6 ms 6228 KB Output is correct
21 Correct 6 ms 6228 KB Output is correct
22 Correct 6 ms 6228 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 4 ms 6100 KB Output is correct
25 Correct 6 ms 6228 KB Output is correct
26 Correct 3 ms 6220 KB Output is correct
27 Correct 4 ms 6228 KB Output is correct
28 Correct 3 ms 5972 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 6 ms 6228 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 5 ms 6228 KB Output is correct
8 Correct 6 ms 6188 KB Output is correct
9 Correct 6 ms 6228 KB Output is correct
10 Correct 4 ms 6232 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 3 ms 6100 KB Output is correct
13 Correct 3 ms 6100 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 4 ms 6228 KB Output is correct
17 Correct 4 ms 6228 KB Output is correct
18 Correct 4 ms 6228 KB Output is correct
19 Correct 3 ms 5972 KB Output is correct
20 Correct 6 ms 6228 KB Output is correct
21 Correct 6 ms 6228 KB Output is correct
22 Correct 6 ms 6228 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 4 ms 6100 KB Output is correct
25 Correct 6 ms 6228 KB Output is correct
26 Correct 3 ms 6220 KB Output is correct
27 Correct 4 ms 6228 KB Output is correct
28 Correct 3 ms 5972 KB Output is correct
29 Correct 6 ms 6356 KB Output is correct
30 Correct 5 ms 6356 KB Output is correct
31 Correct 7 ms 6380 KB Output is correct
32 Correct 7 ms 6228 KB Output is correct
33 Correct 4 ms 6228 KB Output is correct
34 Correct 6 ms 6228 KB Output is correct
35 Correct 6 ms 6228 KB Output is correct
36 Correct 5 ms 6304 KB Output is correct
37 Correct 5 ms 6228 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 4 ms 6228 KB Output is correct
4 Correct 6 ms 6228 KB Output is correct
5 Correct 4 ms 6228 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 5 ms 6228 KB Output is correct
8 Correct 6 ms 6188 KB Output is correct
9 Correct 6 ms 6228 KB Output is correct
10 Correct 4 ms 6232 KB Output is correct
11 Correct 5 ms 6228 KB Output is correct
12 Correct 3 ms 6100 KB Output is correct
13 Correct 3 ms 6100 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 4 ms 6228 KB Output is correct
17 Correct 4 ms 6228 KB Output is correct
18 Correct 4 ms 6228 KB Output is correct
19 Correct 3 ms 5972 KB Output is correct
20 Correct 6 ms 6228 KB Output is correct
21 Correct 6 ms 6228 KB Output is correct
22 Correct 6 ms 6228 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 4 ms 6100 KB Output is correct
25 Correct 6 ms 6228 KB Output is correct
26 Correct 3 ms 6220 KB Output is correct
27 Correct 4 ms 6228 KB Output is correct
28 Correct 3 ms 5972 KB Output is correct
29 Correct 6 ms 6356 KB Output is correct
30 Correct 5 ms 6356 KB Output is correct
31 Correct 7 ms 6380 KB Output is correct
32 Correct 7 ms 6228 KB Output is correct
33 Correct 4 ms 6228 KB Output is correct
34 Correct 6 ms 6228 KB Output is correct
35 Correct 6 ms 6228 KB Output is correct
36 Correct 5 ms 6304 KB Output is correct
37 Correct 5 ms 6228 KB Output is correct
38 Correct 51 ms 12704 KB Output is correct
39 Correct 70 ms 74216 KB Output is correct
40 Correct 67 ms 12528 KB Output is correct
41 Correct 97 ms 12484 KB Output is correct
42 Correct 75 ms 12592 KB Output is correct
43 Correct 34 ms 10212 KB Output is correct
44 Correct 37 ms 7440 KB Output is correct
45 Correct 108 ms 66484 KB Output is correct
46 Correct 110 ms 66492 KB Output is correct
47 Correct 78 ms 70776 KB Output is correct
48 Correct 99 ms 70828 KB Output is correct
49 Correct 88 ms 66796 KB Output is correct
50 Correct 94 ms 66884 KB Output is correct
51 Correct 72 ms 66380 KB Output is correct
52 Correct 81 ms 66396 KB Output is correct
53 Correct 26 ms 13400 KB Output is correct
54 Correct 131 ms 66636 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 2 ms 5972 KB Output is correct
4 Correct 4 ms 5972 KB Output is correct
5 Correct 10 ms 6060 KB Output is correct
6 Correct 3 ms 6100 KB Output is correct
7 Correct 4 ms 6216 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 3 ms 6100 KB Output is correct
11 Correct 3 ms 5972 KB Output is correct
12 Correct 7 ms 6304 KB Output is correct
13 Correct 35 ms 6300 KB Output is correct
14 Correct 60 ms 6100 KB Output is correct
15 Correct 47 ms 6220 KB Output is correct
16 Correct 231 ms 87436 KB Output is correct
17 Correct 1277 ms 174456 KB Output is correct
18 Correct 2788 ms 271480 KB Output is correct
19 Correct 578 ms 108220 KB Output is correct
20 Correct 461 ms 108756 KB Output is correct
21 Correct 646 ms 108720 KB Output is correct
22 Correct 1309 ms 175576 KB Output is correct
23 Correct 715 ms 175568 KB Output is correct
24 Correct 1010 ms 176740 KB Output is correct
25 Correct 851 ms 176440 KB Output is correct
26 Correct 1057 ms 177364 KB Output is correct
27 Correct 2375 ms 222496 KB Output is correct
28 Correct 1666 ms 228168 KB Output is correct
29 Correct 1638 ms 216276 KB Output is correct
30 Correct 1101 ms 159880 KB Output is correct
31 Correct 892 ms 162192 KB Output is correct
32 Correct 1220 ms 157552 KB Output is correct
33 Correct 909 ms 160368 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6016 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 2 ms 5972 KB Output is correct
4 Correct 15 ms 6172 KB Output is correct
5 Correct 31 ms 6176 KB Output is correct
6 Correct 4 ms 6256 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 6 ms 6356 KB Output is correct
9 Correct 50 ms 12688 KB Output is correct
10 Correct 76 ms 74332 KB Output is correct
11 Correct 10 ms 5972 KB Output is correct
12 Correct 53 ms 6188 KB Output is correct
13 Correct 354 ms 162360 KB Output is correct
14 Correct 397 ms 167424 KB Output is correct
15 Correct 1000 ms 176696 KB Output is correct
16 Correct 2867 ms 294400 KB Output is correct
17 Correct 501 ms 201676 KB Output is correct
18 Correct 574 ms 224804 KB Output is correct
19 Correct 467 ms 191564 KB Output is correct
20 Correct 593 ms 189844 KB Output is correct
21 Execution timed out 5078 ms 878220 KB Time limit exceeded
22 Halted 0 ms 0 KB -