oj.uz

Submission #815036

# Submission time Handle Problem Language Result Execution time Memory
815036 2023-08-08T11:52:52 Z WonderfulWhale Jail (JOI22_jail) C++17
72 / 100
 5000 ms 595608 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);
	int a=tab[x].st, b=tab[x].nd;
	for (; head[a] != head[b]; b=p[head[b]]) {
		if (dep[head[a]] > dep[head[b]]) swap(a, b);
		int l = pos[head[b]]+seg1.T, r = pos[b]+seg1.T;
		int X = l;
		while(sz(seg1.t[X])) {
			auto it = seg1.t[X].begin();
			if(*it==x) {
				if(sz(seg1.t[X])==1) break;
				it++;
			}
			int y = *it;
			//cout << "checking: " << y << " for: " << x << "\n";
			if(col[y]==1) return false;
			if(col[y]==0&&!dfs2(y)) return false;
			seg1.t[X].erase(y);
		}
		if(l!=r) {
			X = r;
			while(sz(seg1.t[X])) {
				auto it = seg1.t[X].begin();
				if(*it==x) {
					if(sz(seg1.t[X])==1) break;
					it++;
				}
				int y = *it;
				//cout << "checking: " << y << " for: " << x << "\n";
				if(col[y]==1) return false;
				if(col[y]==0&&!dfs2(y)) return false;
				seg1.t[X].erase(y);
			}
		}
		while(l/2!=r/2) {
			if(l%2==0) {
				X = l+1;
				while(sz(seg1.t[X])) {
					auto it = seg1.t[X].begin();
					if(*it==x) {
						if(sz(seg1.t[X])==1) break;
						it++;
					}
					int y = *it;
					//cout << "checking: " << y << " for: " << x << "\n";
					if(col[y]==1) return false;
					if(col[y]==0&&!dfs2(y)) return false;
					seg1.t[X].erase(y);
				}
			}
			if(r%2==1) {
				X = r-1;
				while(sz(seg1.t[X])) {
					auto it = seg1.t[X].begin();
					if(*it==x) {
						if(sz(seg1.t[X])==1) break;
						it++;
					}
					int y = *it;
					//cout << "checking: " << y << " for: " << x << "\n";
					if(col[y]==1) return false;
					if(col[y]==0&&!dfs2(y)) return false;
					seg1.t[X].erase(y);
				}
			}
			l/=2;
			r/=2;
		}
	}
	if (dep[a] > dep[b]) swap(a, b);
	int l = pos[a]+seg1.T, r = pos[b]+seg1.T;
	int X = l;
	while(sz(seg1.t[X])) {
		auto it = seg1.t[X].begin();
		if(*it==x) {
			if(sz(seg1.t[X])==1) break;
			it++;
		}
		int y = *it;
		//cout << "checking: " << y << " for: " << x << "\n";
		if(col[y]==1) return false;
		if(col[y]==0&&!dfs2(y)) return false;
		seg1.t[X].erase(y);
	}
	if(l!=r) {
		X = r;
		while(sz(seg1.t[X])) {
			auto it = seg1.t[X].begin();
			if(*it==x) {
				if(sz(seg1.t[X])==1) break;
				it++;
			}
			int y = *it;
			//cout << "checking: " << y << " for: " << x << "\n";
			if(col[y]==1) return false;
			if(col[y]==0&&!dfs2(y)) return false;
			seg1.t[X].erase(y);
		}
	}
	while(l/2!=r/2) {
		if(l%2==0) {
			X = l+1;
			while(sz(seg1.t[X])) {
				auto it = seg1.t[X].begin();
				if(*it==x) {
					if(sz(seg1.t[X])==1) break;
					it++;
				}
				int y = *it;
				//cout << "checking: " << y << " for: " << x << "\n";
				if(col[y]==1) return false;
				if(col[y]==0&&!dfs2(y)) return false;
				seg1.t[X].erase(y);
			}
		}
		if(r%2==1) {
			X = r-1;
			while(sz(seg1.t[X])) {
				auto it = seg1.t[X].begin();
				if(*it==x) {
					if(sz(seg1.t[X])==1) break;
					it++;
				}
				int y = *it;
				//cout << "checking: " << y << " for: " << x << "\n";
				if(col[y]==1) return false;
				if(col[y]==0&&!dfs2(y)) return false;
				seg1.t[X].erase(y);
			}
		}
		l/=2;
		r/=2;
	}
	Gg += sz(v1);
	//assert(Gg<=2*N);
	 X = pos[tab[x].nd];
	X+=seg2.T;
	while(X) {
		while(sz(seg2.t[X])) {
			auto it = seg2.t[X].begin();
			if(*it==x) {
				if(sz(seg2.t[X])==1) break;
				it++;
			}
			int y = *it;
			//cout << "checking: " << y << " for: " << x << "\n";
			if(col[y]==1) return false;
			if(col[y]==0&&!dfs2(y)) return false;
			seg2.t[X].erase(y);
		}
		X/=2;
	}
	//assert(Gg<=2*N);
	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 5972 KB Output is correct
2 Correct 3 ms 5972 KB Output is correct
3 Correct 3 ms 5984 KB Output is correct
4 Correct 19 ms 6356 KB Output is correct
5 Correct 30 ms 6356 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 6 ms 6356 KB Output is correct
9 Correct 52 ms 13032 KB Output is correct
10 Correct 70 ms 74500 KB Output is correct
11 Correct 11 ms 6096 KB Output is correct
12 Correct 64 ms 6480 KB Output is correct
13 Correct 368 ms 162500 KB Output is correct
14 Correct 418 ms 167640 KB Output is correct
15 Correct 966 ms 177092 KB Output is correct
16 Execution timed out 5041 ms 595608 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 4 ms 6232 KB Output is correct
4 Correct 5 ms 6244 KB Output is correct
5 Correct 5 ms 6224 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 4 ms 6220 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 4 ms 6228 KB Output is correct
13 Correct 4 ms 6232 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 4 ms 6232 KB Output is correct
4 Correct 5 ms 6244 KB Output is correct
5 Correct 5 ms 6224 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 4 ms 6220 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 4 ms 6228 KB Output is correct
13 Correct 4 ms 6232 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 5 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 4 ms 6228 KB Output is correct
21 Correct 4 ms 6228 KB Output is correct
22 Correct 4 ms 6232 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 4 ms 6100 KB Output is correct
25 Correct 5 ms 6220 KB Output is correct
26 Correct 3 ms 6220 KB Output is correct
27 Correct 6 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 5964 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 4 ms 6232 KB Output is correct
4 Correct 5 ms 6244 KB Output is correct
5 Correct 5 ms 6224 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 4 ms 6220 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 4 ms 6228 KB Output is correct
13 Correct 4 ms 6232 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 5 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 4 ms 6228 KB Output is correct
21 Correct 4 ms 6228 KB Output is correct
22 Correct 4 ms 6232 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 4 ms 6100 KB Output is correct
25 Correct 5 ms 6220 KB Output is correct
26 Correct 3 ms 6220 KB Output is correct
27 Correct 6 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 6360 KB Output is correct
31 Correct 5 ms 6388 KB Output is correct
32 Correct 5 ms 6356 KB Output is correct
33 Correct 4 ms 6228 KB Output is correct
34 Correct 7 ms 6268 KB Output is correct
35 Correct 6 ms 6228 KB Output is correct
36 Correct 5 ms 6228 KB Output is correct
37 Correct 6 ms 6228 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5964 KB Output is correct
2 Correct 3 ms 5960 KB Output is correct
3 Correct 4 ms 6232 KB Output is correct
4 Correct 5 ms 6244 KB Output is correct
5 Correct 5 ms 6224 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 4 ms 6220 KB Output is correct
9 Correct 4 ms 6228 KB Output is correct
10 Correct 4 ms 6228 KB Output is correct
11 Correct 4 ms 6228 KB Output is correct
12 Correct 4 ms 6228 KB Output is correct
13 Correct 4 ms 6232 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 5 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 4 ms 6228 KB Output is correct
21 Correct 4 ms 6228 KB Output is correct
22 Correct 4 ms 6232 KB Output is correct
23 Correct 3 ms 5972 KB Output is correct
24 Correct 4 ms 6100 KB Output is correct
25 Correct 5 ms 6220 KB Output is correct
26 Correct 3 ms 6220 KB Output is correct
27 Correct 6 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 6360 KB Output is correct
31 Correct 5 ms 6388 KB Output is correct
32 Correct 5 ms 6356 KB Output is correct
33 Correct 4 ms 6228 KB Output is correct
34 Correct 7 ms 6268 KB Output is correct
35 Correct 6 ms 6228 KB Output is correct
36 Correct 5 ms 6228 KB Output is correct
37 Correct 6 ms 6228 KB Output is correct
38 Correct 63 ms 13088 KB Output is correct
39 Correct 76 ms 74616 KB Output is correct
40 Correct 65 ms 12872 KB Output is correct
41 Correct 76 ms 12860 KB Output is correct
42 Correct 59 ms 12992 KB Output is correct
43 Correct 35 ms 10652 KB Output is correct
44 Correct 28 ms 7656 KB Output is correct
45 Correct 112 ms 66992 KB Output is correct
46 Correct 113 ms 66964 KB Output is correct
47 Correct 86 ms 71144 KB Output is correct
48 Correct 81 ms 71132 KB Output is correct
49 Correct 87 ms 67204 KB Output is correct
50 Correct 91 ms 67260 KB Output is correct
51 Correct 74 ms 66728 KB Output is correct
52 Correct 75 ms 66692 KB Output is correct
53 Correct 31 ms 13520 KB Output is correct
54 Correct 118 ms 67000 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5944 KB Output is correct
2 Correct 3 ms 5916 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 3 ms 5920 KB Output is correct
5 Correct 11 ms 6104 KB Output is correct
6 Correct 3 ms 6228 KB Output is correct
7 Correct 4 ms 6232 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 5 ms 6228 KB Output is correct
13 Correct 36 ms 6444 KB Output is correct
14 Correct 61 ms 6452 KB Output is correct
15 Correct 48 ms 6432 KB Output is correct
16 Correct 197 ms 87588 KB Output is correct
17 Correct 1188 ms 174732 KB Output is correct
18 Correct 2774 ms 271652 KB Output is correct
19 Correct 619 ms 108476 KB Output is correct
20 Correct 421 ms 108892 KB Output is correct
21 Correct 583 ms 108984 KB Output is correct
22 Correct 1370 ms 175896 KB Output is correct
23 Correct 884 ms 175428 KB Output is correct
24 Correct 958 ms 176740 KB Output is correct
25 Correct 841 ms 177236 KB Output is correct
26 Correct 1129 ms 177472 KB Output is correct
27 Correct 2332 ms 224544 KB Output is correct
28 Correct 1799 ms 230696 KB Output is correct
29 Correct 1758 ms 217860 KB Output is correct
30 Correct 1189 ms 159960 KB Output is correct
31 Correct 854 ms 162064 KB Output is correct
32 Correct 1140 ms 159000 KB Output is correct
33 Correct 1024 ms 161976 KB Output is correct

Subtask #7
0 / 23.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 3 ms 5984 KB Output is correct
4 Correct 19 ms 6356 KB Output is correct
5 Correct 30 ms 6356 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 4 ms 6228 KB Output is correct
8 Correct 6 ms 6356 KB Output is correct
9 Correct 52 ms 13032 KB Output is correct
10 Correct 70 ms 74500 KB Output is correct
11 Correct 11 ms 6096 KB Output is correct
12 Correct 64 ms 6480 KB Output is correct
13 Correct 368 ms 162500 KB Output is correct
14 Correct 418 ms 167640 KB Output is correct
15 Correct 966 ms 177092 KB Output is correct
16 Execution timed out 5041 ms 595608 KB Time limit exceeded
17 Halted 0 ms 0 KB -