oj.uz

Submission #815044

# Submission time Handle Problem Language Result Execution time Memory
815044 2023-08-08T11:56:28 Z WonderfulWhale Jail (JOI22_jail) C++17
5 / 100
 5000 ms 619972 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";
			seg1.t[X].erase(y);
			if(col[y]==1) return false;
			if(col[y]==0&&!dfs2(y)) return false;
		}
		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";
				seg1.t[X].erase(y);
				if(col[y]==1) return false;
				if(col[y]==0&&!dfs2(y)) return false;
			}
		}
		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";
					seg1.t[X].erase(y);
					if(col[y]==1) return false;
					if(col[y]==0&&!dfs2(y)) return false;
				}
			}
			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";
					seg1.t[X].erase(y);
					if(col[y]==1) return false;
					if(col[y]==0&&!dfs2(y)) return false;
				}
			}
			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";
		seg1.t[X].erase(y);
		if(col[y]==1) return false;
		if(col[y]==0&&!dfs2(y)) return false;
	}
	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";
			seg1.t[X].erase(y);
			if(col[y]==1) return false;
			if(col[y]==0&&!dfs2(y)) return false;
		}
	}
	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";
				seg1.t[X].erase(y);
				if(col[y]==1) return false;
				if(col[y]==0&&!dfs2(y)) return false;
			}
		}
		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";
				seg1.t[X].erase(y);
				if(col[y]==1) return false;
				if(col[y]==0&&!dfs2(y)) return false;
			}
		}
		l/=2;
		r/=2;
	}
	//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";
			seg2.t[X].erase(y);
			if(col[y]==1) return false;
			if(col[y]==0&&!dfs2(y)) return false;
		}
		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 5964 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 15 ms 6484 KB Output is correct
5 Correct 30 ms 6900 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 6408 KB Output is correct
9 Correct 64 ms 13504 KB Output is correct
10 Correct 74 ms 74956 KB Output is correct
11 Correct 11 ms 6108 KB Output is correct
12 Correct 55 ms 7252 KB Output is correct
13 Correct 350 ms 163140 KB Output is correct
14 Correct 387 ms 168140 KB Output is correct
15 Correct 992 ms 177652 KB Output is correct
16 Execution timed out 5073 ms 619972 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 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 4 ms 6228 KB Output is correct
5 Correct 5 ms 6228 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 6228 KB Output is correct
9 Correct 4 ms 6256 KB Output is correct
10 Correct 4 ms 6256 KB Output is correct
11 Correct 4 ms 6232 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 3 ms 6228 KB Output is correct

Subtask #3
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 4 ms 6228 KB Output is correct
5 Correct 5 ms 6228 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 6228 KB Output is correct
9 Correct 4 ms 6256 KB Output is correct
10 Correct 4 ms 6256 KB Output is correct
11 Correct 4 ms 6232 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 3 ms 6228 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 6 ms 6228 KB Output is correct
17 Correct 5 ms 6264 KB Output is correct
18 Correct 4 ms 6228 KB Output is correct
19 Correct 3 ms 5972 KB Output is correct
20 Incorrect 4 ms 6228 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
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 4 ms 6228 KB Output is correct
5 Correct 5 ms 6228 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 6228 KB Output is correct
9 Correct 4 ms 6256 KB Output is correct
10 Correct 4 ms 6256 KB Output is correct
11 Correct 4 ms 6232 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 3 ms 6228 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 6 ms 6228 KB Output is correct
17 Correct 5 ms 6264 KB Output is correct
18 Correct 4 ms 6228 KB Output is correct
19 Correct 3 ms 5972 KB Output is correct
20 Incorrect 4 ms 6228 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
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 4 ms 6228 KB Output is correct
5 Correct 5 ms 6228 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 6228 KB Output is correct
9 Correct 4 ms 6256 KB Output is correct
10 Correct 4 ms 6256 KB Output is correct
11 Correct 4 ms 6232 KB Output is correct
12 Correct 3 ms 6228 KB Output is correct
13 Correct 3 ms 6228 KB Output is correct
14 Correct 3 ms 5972 KB Output is correct
15 Correct 3 ms 5972 KB Output is correct
16 Correct 6 ms 6228 KB Output is correct
17 Correct 5 ms 6264 KB Output is correct
18 Correct 4 ms 6228 KB Output is correct
19 Correct 3 ms 5972 KB Output is correct
20 Incorrect 4 ms 6228 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #6
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 3 ms 5972 KB Output is correct
4 Correct 3 ms 5964 KB Output is correct
5 Correct 11 ms 6104 KB Output is correct
6 Correct 4 ms 6228 KB Output is correct
7 Correct 3 ms 6236 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5972 KB Output is correct
10 Correct 4 ms 6092 KB Output is correct
11 Correct 3 ms 5972 KB Output is correct
12 Correct 8 ms 6304 KB Output is correct
13 Incorrect 37 ms 6760 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5972 KB Output is correct
2 Correct 3 ms 5964 KB Output is correct
3 Correct 3 ms 5972 KB Output is correct
4 Correct 15 ms 6484 KB Output is correct
5 Correct 30 ms 6900 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 6408 KB Output is correct
9 Correct 64 ms 13504 KB Output is correct
10 Correct 74 ms 74956 KB Output is correct
11 Correct 11 ms 6108 KB Output is correct
12 Correct 55 ms 7252 KB Output is correct
13 Correct 350 ms 163140 KB Output is correct
14 Correct 387 ms 168140 KB Output is correct
15 Correct 992 ms 177652 KB Output is correct
16 Execution timed out 5073 ms 619972 KB Time limit exceeded
17 Halted 0 ms 0 KB -