Submission #777934

#	Time	Username	Problem	Language	Result	Execution time	Memory
777934		aZvezda	Jail (JOI22_jail)	C++14	100 / 100	1291 ms	167568 KiB

jail

#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 = 1e6 + 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);
	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;
	cerr << "Starting " << x << endl;
 
	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] + 1;
		} else {
			return in[quer[ret.second].first];
		}
		return -1;
	};
 
 	cerr << "Searching for kid " << x << " " << in[b] << " " << out[b] << endl;
	while(true) {
		auto now = st.ans(1, 0, MAX_N - 1, in[b], out[b]);
		cerr << "Found " << x << " " << now.mx.first << " " << now.mx.second << " " << now.mn.first << endl;
		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 <= 2 * n + 10; i ++) { st.upd(1, 0, MAX_N - 1, i); }
	for(int i = 0; i <= 2 * 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] + 1, {in[a], i});
		st_ex.upd(1, 0, MAX_N - 1, in[a], {i, -1});
		cerr << "Quer " << i << " " << a << " " << b << " -> " << 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]);
		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 (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23