oj.uz

답안 #777917

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777917 2023-07-09T22:33:48 Z aZvezda Jail (JOI22_jail) C++14
10 / 100
 639 ms 69804 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

#ifndef LOCAL
#define cerr if(false)cerr
#endif

const int MAX_N = 2e5 + 10, LOG = 20;
int n, m, par[MAX_N][LOG], d[MAX_N], in[MAX_N], out[MAX_N], tme;
int sz[MAX_N], chain[MAX_N];
pair<int, int> quer[MAX_N];
vector<int> g[MAX_N], eul;

void calc(int x, int p) {
	sz[x] = 1;
	d[x] = d[p] + 1;
	par[x][0] = p;
	for(int i = 1; i < LOG; i ++) {
		par[x][i] = par[par[x][i - 1]][i - 1];
	}
	for(auto it : g[x]) {
		if(it == p) { continue; }
		calc(it, x);
		sz[x] += sz[it];
	}
}

void dfs(int x, int p, bool big = false) {
	if(big) {
		chain[x] = chain[p];
	} else {
		chain[x] = x;
	}

	in[x] = eul.size();
	eul.push_back(x);

	int heavy = -1;
	for(auto it : g[x]) {
		if(it == p) { continue; }
		if(heavy == -1 || sz[it] > sz[heavy]) {
			heavy = it;
		}
	}

	if(heavy != -1) { dfs(heavy, x, true); }
	for(auto it : g[x]) {
		if(it == p || it == heavy) { continue; }
		dfs(it, x, false);
	}

	out[x] = eul.size() - 1;
}

int lca(int a, int b) {
	if(d[a] < d[b]) { swap(a, b); }
	for(int i = LOG - 1; i >= 0; i --) {
		if(d[par[a][i]] >= d[b]) {
			a = par[a][i];
		}
	}
	if(a == b) { return a; }
	for(int i = LOG - 1; i >= 0; i --) {
		if(par[a][i] != par[b][i]) {
			a = par[a][i];
			b = par[b][i];
		}
	}
	return par[a][0];
}

struct node_sim {
	pair<int, int> mn, mx;
	node_sim() { mn = {mod, -1}; mx = {-mod, -1}; }
	node_sim(const pair<int, int> &x) { mn = mx = x; }
	node_sim operator +(const node_sim &other) const {
		node_sim ret;
		ret.mn = mn.first < other.mn.first ? mn : other.mn;
		ret.mx = mx.first > other.mx.first ? mx : other.mx;
		return ret;
	}
};

struct node_ex {
	int val;
	node_ex(const pair<int, int> &_val = {-1, -1}) { val = _val.first; }
	node_ex operator +(const node_ex &other) const {
		node_ex ret;
		ret.val = val != -1 ? val : other.val;
		return ret;
	}
};

template<class node>
struct seg_tree {
	node tree[4 * MAX_N];
	void upd(int curr, int l, int r, int ind, const pair<int, int> &val = {-1, -1}) {
		if(l == r && l == ind) {
			if(val.first == -1) {
				tree[curr] = node();
			} else {
				tree[curr] = node(val);
			}
			return;
		} else if(l > ind || r < ind) { return; }
		int m = (l + r) / 2ll;
		upd(curr * 2, l, m, ind, val);
		upd(curr * 2 + 1, m + 1, r, ind, val);
		tree[curr] = tree[curr * 2] + tree[curr * 2 + 1]; 
	}
	node ans(int curr, int l, int r,  int ql, int qr) {
		if(ql <= l && r <= qr) {
			return tree[curr];
		} else if(l > qr || r < ql) { return node(); }
		int m = (l + r) / 2ll;
		return ans(curr * 2, l, m, ql, qr) + ans(curr * 2 + 1, m + 1, r, ql, qr);
	}
};

seg_tree<node_sim> st;
seg_tree<node_ex> st_ex;

vector<int> ret = {};
vector<int> who[MAX_N];
int used[MAX_N];

int find_block(int a, int b) {
	node_ex ans;
	while(chain[a] != chain[b]) {
		if(d[chain[a]] < d[chain[b]]) { swap(a, b); }
		ans = ans + st_ex.ans(1, 0, MAX_N - 1, in[chain[a]], in[a]);
		a = par[chain[a]][0];
	}
	if(d[a] > d[b]) { swap(a, b); }
	ans = ans + st_ex.ans(1, 0, MAX_N - 1, in[a], in[b]);
	return ans.val;
}


void topo(int x) {
	if(used[x]) { return; }
	used[x] = true;

	int a = quer[x].first, b = quer[x].second;
	st_ex.upd(1, 0, MAX_N - 1, in[a]);

	int bl;
	while((bl = find_block(a, b)) != -1) {
		st_ex.upd(1, 0, MAX_N - 1, in[quer[bl].first]);
		topo(bl);
	}

	const auto find = [&](const auto ret) {
		if(in[quer[ret.second].first] == ret.first) {
			return in[quer[ret.second].second];
		} else {
			return in[quer[ret.second].first];
		}
		return -1;
	};
	
	for(auto it : who[b]) { topo(it); }
	while(true) {
		auto now = st.ans(1, 0, MAX_N - 1, in[b], out[b]);
		if(now.mx.first > out[b]) {
			st.upd(1, 0, MAX_N - 1, find(now.mx));
			topo(now.mx.second);
		} else if(now.mn.first <= in[b]) {
			st.upd(1, 0, MAX_N - 1, find(now.mn));
			topo(now.mn.second);
		} else {
			break;
		}
	}

	ret.push_back(x);
}

void reset() {
	for(int i = 0; i <= n + 10; i ++) { st.upd(1, 0, MAX_N - 1, i); }
	for(int i = 0; i <= n + 10; i ++) { st_ex.upd(1, 0, MAX_N - 1, i); }
}

void solve() {
	reset();
	eul.resize(0);
	for(int i = 1; i <= n; i ++) {
		who[i].resize(0);
		g[i].resize(0);
	}
	fill_n(used, m + 1, false); 

	cin >> n;
	for(int i = 0; i < n - 1; i ++) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	calc(1, 0);
	dfs(1, 0, false);
	
	cin >> m;
	for(int i = 0; i < m; i ++) {
		int a, b;
		cin >> a >> b;
		quer[i] = {a, b};
		who[lca(a, b)].push_back(i);
		st.upd(1, 0, MAX_N - 1, in[a], {in[b], i});
		st.upd(1, 0, MAX_N - 1, in[b], {in[a], i});
		st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
	}

	ret = {};
	for(int i = 0; i < m; i ++) {
		if(!used[i]) {
			topo(i);
		}
	}
	
	reset();
	for(int i = 0; i < m; i ++) {
		int a = quer[i].first, b = quer[i].second;
		st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
	}

	for(auto it : ret) {
		int a = quer[it].first;
		int b = quer[it].second;

		st_ex.upd(1, 0, MAX_N - 1, in[a]);
		if(find_block(a, b) != -1) {
			cout << "No" << endl;
			return;
		}
		st_ex.upd(1, 0, MAX_N - 1, in[b], {it, -1});
	}
	cout << "Yes" << endl;
}

signed main() {
	// ios_base::sync_with_stdio(false); cin.tie(NULL);

	int t;
	cin >> t;
	while(t --) {
		solve();
	}
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:225:26: warning: unused variable 'b' [-Wunused-variable]
  225 |   int a = quer[i].first, b = quer[i].second;
      |                          ^

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 11 ms 25300 KB Output is correct
4 Correct 64 ms 25428 KB Output is correct
5 Correct 104 ms 25428 KB Output is correct
6 Correct 15 ms 25428 KB Output is correct
7 Correct 17 ms 25428 KB Output is correct
8 Correct 20 ms 25356 KB Output is correct
9 Correct 146 ms 26796 KB Output is correct
10 Correct 129 ms 50860 KB Output is correct
11 Correct 42 ms 25300 KB Output is correct
12 Correct 177 ms 25420 KB Output is correct
13 Correct 236 ms 53296 KB Output is correct
14 Correct 273 ms 53332 KB Output is correct
15 Correct 347 ms 53084 KB Output is correct
16 Correct 639 ms 64756 KB Output is correct
17 Correct 268 ms 55684 KB Output is correct
18 Correct 398 ms 69804 KB Output is correct
19 Correct 290 ms 53932 KB Output is correct
20 Correct 251 ms 53740 KB Output is correct
21 Correct 259 ms 55584 KB Output is correct
22 Correct 270 ms 53824 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 12 ms 25408 KB Output is correct
3 Correct 16 ms 25372 KB Output is correct
4 Correct 19 ms 25428 KB Output is correct
5 Correct 18 ms 25324 KB Output is correct
6 Correct 15 ms 25428 KB Output is correct
7 Correct 16 ms 25428 KB Output is correct
8 Correct 16 ms 25376 KB Output is correct
9 Correct 16 ms 25428 KB Output is correct
10 Correct 15 ms 25352 KB Output is correct
11 Correct 17 ms 25344 KB Output is correct
12 Correct 13 ms 25408 KB Output is correct
13 Correct 13 ms 25444 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 12 ms 25408 KB Output is correct
3 Correct 16 ms 25372 KB Output is correct
4 Correct 19 ms 25428 KB Output is correct
5 Correct 18 ms 25324 KB Output is correct
6 Correct 15 ms 25428 KB Output is correct
7 Correct 16 ms 25428 KB Output is correct
8 Correct 16 ms 25376 KB Output is correct
9 Correct 16 ms 25428 KB Output is correct
10 Correct 15 ms 25352 KB Output is correct
11 Correct 17 ms 25344 KB Output is correct
12 Correct 13 ms 25408 KB Output is correct
13 Correct 13 ms 25444 KB Output is correct
14 Correct 12 ms 25300 KB Output is correct
15 Correct 11 ms 25340 KB Output is correct
16 Correct 15 ms 25440 KB Output is correct
17 Correct 15 ms 25436 KB Output is correct
18 Correct 19 ms 25364 KB Output is correct
19 Correct 11 ms 25300 KB Output is correct
20 Correct 15 ms 25364 KB Output is correct
21 Correct 16 ms 25436 KB Output is correct
22 Incorrect 15 ms 25428 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 12 ms 25408 KB Output is correct
3 Correct 16 ms 25372 KB Output is correct
4 Correct 19 ms 25428 KB Output is correct
5 Correct 18 ms 25324 KB Output is correct
6 Correct 15 ms 25428 KB Output is correct
7 Correct 16 ms 25428 KB Output is correct
8 Correct 16 ms 25376 KB Output is correct
9 Correct 16 ms 25428 KB Output is correct
10 Correct 15 ms 25352 KB Output is correct
11 Correct 17 ms 25344 KB Output is correct
12 Correct 13 ms 25408 KB Output is correct
13 Correct 13 ms 25444 KB Output is correct
14 Correct 12 ms 25300 KB Output is correct
15 Correct 11 ms 25340 KB Output is correct
16 Correct 15 ms 25440 KB Output is correct
17 Correct 15 ms 25436 KB Output is correct
18 Correct 19 ms 25364 KB Output is correct
19 Correct 11 ms 25300 KB Output is correct
20 Correct 15 ms 25364 KB Output is correct
21 Correct 16 ms 25436 KB Output is correct
22 Incorrect 15 ms 25428 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25300 KB Output is correct
2 Correct 12 ms 25408 KB Output is correct
3 Correct 16 ms 25372 KB Output is correct
4 Correct 19 ms 25428 KB Output is correct
5 Correct 18 ms 25324 KB Output is correct
6 Correct 15 ms 25428 KB Output is correct
7 Correct 16 ms 25428 KB Output is correct
8 Correct 16 ms 25376 KB Output is correct
9 Correct 16 ms 25428 KB Output is correct
10 Correct 15 ms 25352 KB Output is correct
11 Correct 17 ms 25344 KB Output is correct
12 Correct 13 ms 25408 KB Output is correct
13 Correct 13 ms 25444 KB Output is correct
14 Correct 12 ms 25300 KB Output is correct
15 Correct 11 ms 25340 KB Output is correct
16 Correct 15 ms 25440 KB Output is correct
17 Correct 15 ms 25436 KB Output is correct
18 Correct 19 ms 25364 KB Output is correct
19 Correct 11 ms 25300 KB Output is correct
20 Correct 15 ms 25364 KB Output is correct
21 Correct 16 ms 25436 KB Output is correct
22 Incorrect 15 ms 25428 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25328 KB Output is correct
2 Correct 13 ms 25300 KB Output is correct
3 Correct 16 ms 25292 KB Output is correct
4 Correct 11 ms 25300 KB Output is correct
5 Correct 44 ms 25300 KB Output is correct
6 Correct 14 ms 25336 KB Output is correct
7 Correct 14 ms 25412 KB Output is correct
8 Correct 11 ms 25300 KB Output is correct
9 Correct 12 ms 25372 KB Output is correct
10 Correct 11 ms 25376 KB Output is correct
11 Correct 12 ms 25300 KB Output is correct
12 Correct 19 ms 25352 KB Output is correct
13 Incorrect 124 ms 25420 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 11 ms 25300 KB Output is correct
4 Correct 64 ms 25428 KB Output is correct
5 Correct 104 ms 25428 KB Output is correct
6 Correct 15 ms 25428 KB Output is correct
7 Correct 17 ms 25428 KB Output is correct
8 Correct 20 ms 25356 KB Output is correct
9 Correct 146 ms 26796 KB Output is correct
10 Correct 129 ms 50860 KB Output is correct
11 Correct 42 ms 25300 KB Output is correct
12 Correct 177 ms 25420 KB Output is correct
13 Correct 236 ms 53296 KB Output is correct
14 Correct 273 ms 53332 KB Output is correct
15 Correct 347 ms 53084 KB Output is correct
16 Correct 639 ms 64756 KB Output is correct
17 Correct 268 ms 55684 KB Output is correct
18 Correct 398 ms 69804 KB Output is correct
19 Correct 290 ms 53932 KB Output is correct
20 Correct 251 ms 53740 KB Output is correct
21 Correct 259 ms 55584 KB Output is correct
22 Correct 270 ms 53824 KB Output is correct
23 Correct 12 ms 25300 KB Output is correct
24 Correct 12 ms 25408 KB Output is correct
25 Correct 16 ms 25372 KB Output is correct
26 Correct 19 ms 25428 KB Output is correct
27 Correct 18 ms 25324 KB Output is correct
28 Correct 15 ms 25428 KB Output is correct
29 Correct 16 ms 25428 KB Output is correct
30 Correct 16 ms 25376 KB Output is correct
31 Correct 16 ms 25428 KB Output is correct
32 Correct 15 ms 25352 KB Output is correct
33 Correct 17 ms 25344 KB Output is correct
34 Correct 13 ms 25408 KB Output is correct
35 Correct 13 ms 25444 KB Output is correct
36 Correct 12 ms 25300 KB Output is correct
37 Correct 11 ms 25340 KB Output is correct
38 Correct 15 ms 25440 KB Output is correct
39 Correct 15 ms 25436 KB Output is correct
40 Correct 19 ms 25364 KB Output is correct
41 Correct 11 ms 25300 KB Output is correct
42 Correct 15 ms 25364 KB Output is correct
43 Correct 16 ms 25436 KB Output is correct
44 Incorrect 15 ms 25428 KB Output isn't correct
45 Halted 0 ms 0 KB -