oj.uz

답안 #777931

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
777931 2023-07-09T22:51:51 Z aZvezda Jail (JOI22_jail) C++14
5 / 100
 18 ms 25428 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;

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

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 25300 KB Output is correct
2 Incorrect 12 ms 25288 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25340 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 18 ms 25364 KB Output is correct
4 Correct 15 ms 25428 KB Output is correct
5 Correct 15 ms 25340 KB Output is correct
6 Correct 16 ms 25428 KB Output is correct
7 Correct 15 ms 25428 KB Output is correct
8 Correct 15 ms 25428 KB Output is correct
9 Correct 15 ms 25428 KB Output is correct
10 Correct 18 ms 25428 KB Output is correct
11 Correct 15 ms 25324 KB Output is correct
12 Correct 14 ms 25332 KB Output is correct
13 Correct 14 ms 25324 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25340 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 18 ms 25364 KB Output is correct
4 Correct 15 ms 25428 KB Output is correct
5 Correct 15 ms 25340 KB Output is correct
6 Correct 16 ms 25428 KB Output is correct
7 Correct 15 ms 25428 KB Output is correct
8 Correct 15 ms 25428 KB Output is correct
9 Correct 15 ms 25428 KB Output is correct
10 Correct 18 ms 25428 KB Output is correct
11 Correct 15 ms 25324 KB Output is correct
12 Correct 14 ms 25332 KB Output is correct
13 Correct 14 ms 25324 KB Output is correct
14 Incorrect 12 ms 25300 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25340 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 18 ms 25364 KB Output is correct
4 Correct 15 ms 25428 KB Output is correct
5 Correct 15 ms 25340 KB Output is correct
6 Correct 16 ms 25428 KB Output is correct
7 Correct 15 ms 25428 KB Output is correct
8 Correct 15 ms 25428 KB Output is correct
9 Correct 15 ms 25428 KB Output is correct
10 Correct 18 ms 25428 KB Output is correct
11 Correct 15 ms 25324 KB Output is correct
12 Correct 14 ms 25332 KB Output is correct
13 Correct 14 ms 25324 KB Output is correct
14 Incorrect 12 ms 25300 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 25340 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 18 ms 25364 KB Output is correct
4 Correct 15 ms 25428 KB Output is correct
5 Correct 15 ms 25340 KB Output is correct
6 Correct 16 ms 25428 KB Output is correct
7 Correct 15 ms 25428 KB Output is correct
8 Correct 15 ms 25428 KB Output is correct
9 Correct 15 ms 25428 KB Output is correct
10 Correct 18 ms 25428 KB Output is correct
11 Correct 15 ms 25324 KB Output is correct
12 Correct 14 ms 25332 KB Output is correct
13 Correct 14 ms 25324 KB Output is correct
14 Incorrect 12 ms 25300 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 25300 KB Output is correct
2 Incorrect 11 ms 25316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 25300 KB Output is correct
2 Incorrect 12 ms 25288 KB Output isn't correct
3 Halted 0 ms 0 KB -