oj.uz

Submission #777930

# Submission time Handle Problem Language Result Execution time Memory
777930 2023-07-09T22:50:56 Z aZvezda Jail (JOI22_jail) C++14
5 / 100
 4 ms 596 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;
int n, m, par[MAX_N], 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] = p;
	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) {
	while(chain[a] != chain[b]) {
		if(d[chain[a]] < d[chain[b]]) { swap(a, b); }
		a = par[chain[a]];
	}
	if(d[a] > d[b]) { swap(a, b); }
	return a;
}

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]];
	}
	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;

	cerr << "Starting " << x << endl;

	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;
	};
	
	cerr << " Topo " << x << " " << in[b] << " " << out[b] << endl;
	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;
		}
	}

	cerr << "Ending " << x << endl;

	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});
		cerr << i << " " << in[a] << " " << in[b] << " " << lca(a, b) << endl;
	}

	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) {
		cerr << "look " << it << endl;
		int a = quer[it].first;
		int b = quer[it].second;

		st_ex.upd(1, 0, MAX_N - 1, in[a]);
		auto bl = find_block(a, b);
		cerr << bl << endl;
		if(bl != -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:220:26: warning: unused variable 'b' [-Wunused-variable]
  220 |   int a = quer[i].first, b = quer[i].second;
      |                          ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 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 Incorrect 1 ms 468 KB Output isn't correct
15 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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 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 Incorrect 1 ms 468 KB Output isn't correct
15 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 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 3 ms 596 KB Output is correct
9 Correct 4 ms 596 KB Output is correct
10 Correct 3 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 Incorrect 1 ms 468 KB Output isn't correct
15 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 Incorrect 1 ms 596 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -