oj.uz

Submission #777911

# Submission time Handle Problem Language Result Execution time Memory
777911 2023-07-09T22:25:15 Z aZvezda Jail (JOI22_jail) C++14
5 / 100
 93 ms 1748 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 = 2e3 + 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]);

	for(auto it : who[b]) { topo(it); }
	
	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;
	};

	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, n + 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:226:26: warning: unused variable 'b' [-Wunused-variable]
  226 |   int a = quer[i].first, b = quer[i].second;
      |                          ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 35 ms 864 KB Output is correct
5 Correct 74 ms 864 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 8 ms 572 KB Output is correct
9 Runtime error 4 ms 1748 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 4 ms 572 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 4 ms 572 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 576 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 576 KB Output is correct
19 Correct 1 ms 564 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 4 ms 596 KB Output is correct
22 Incorrect 4 ms 596 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 4 ms 572 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 576 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 576 KB Output is correct
19 Correct 1 ms 564 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 4 ms 596 KB Output is correct
22 Incorrect 4 ms 596 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 4 ms 572 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 5 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 4 ms 596 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 4 ms 468 KB Output is correct
16 Correct 4 ms 576 KB Output is correct
17 Correct 4 ms 596 KB Output is correct
18 Correct 4 ms 576 KB Output is correct
19 Correct 1 ms 564 KB Output is correct
20 Correct 4 ms 596 KB Output is correct
21 Correct 4 ms 596 KB Output is correct
22 Incorrect 4 ms 596 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 564 KB Output is correct
5 Correct 24 ms 704 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 7 ms 596 KB Output is correct
13 Incorrect 93 ms 1092 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 35 ms 864 KB Output is correct
5 Correct 74 ms 864 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 8 ms 572 KB Output is correct
9 Runtime error 4 ms 1748 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -