제출 #602701

#제출 시각아이디문제언어결과실행 시간메모리
602701TigryonochekkJail (JOI22_jail)C++17
5 / 100
27 ms3284 KiB
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <string>
using namespace std;
#define ll long long
#define pii pair<int, int>
const int N = 1.2e5 + 2, lgN = 17, M = 102;

int n, ln;
vector<int> g[N];
int m;
int b[N], w[N];

pii sb[N], sw[N];

int p[N];
int tin[N], tout[N];
int timer;
int d[N][lgN];

set<int> pp[M];
int col[M];

void cleaning() {
	for (int i = 1; i <= n; i++) {
		g[i].clear();
	}
	fill(p + 1, p + n + 1, 0);
	fill(tin, tin + n + 1, 0);
	fill(tout, tout + n + 1, 0);
	timer = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < ln; j++) {
			d[i][j] = 0;
		}
	}
	for (int i = 1; i <= m; i++) {
		pp[i].clear();
	}
}

void dfs(int v) {
	tin[v] = timer++;
	for (int to : g[v]) {
		if (p[v] == to) continue;
		p[to] = v;
		d[to][0] = v;
		for (int i = 1; i < ln; i++) {
			d[to][i] = d[d[to][i - 1]][i - 1];
		}
		dfs(to);
	}
	tout[v] = timer++;
}

bool check(int a, int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}

int lca(int a, int b) {
	if (check(a, b)) return a;
	if (check(b, a)) return b;
	for (int i = ln - 1; i >= 0; i--) {
		if (!check(d[a][i], b))
			a = d[a][i];
	}
	return p[a];
}

bool belong(int a, int b, int c) {
	return check(lca(a, b), c) && (check(c, a) || check(c, b));
}

//bool daunCheck(int i, int j) {
//	if (belong(b[i], w[i], b[j]) && belong(b[j], w[j], b[i]))
//		return 0;
//	if (belong(b[i], w[i], w[j]) && belong(b[j], w[j], w[i]))
//		return 0;
//	if (belong(b[i], w[i], w[j]) && belong(b[i], w[i], b[j]))
//		return 0;
//	if (belong(b[j], w[j], w[i]) && belong(b[j], w[j], b[i]))
//		return 0;
//	return 1;
//}

int compare(int i, int j) { //0 - lriv, 1-skizb, 2-verj, 3-vochinch
	if (belong(b[i], w[i], b[j])) {
		if (belong(b[i], w[i], w[j])) {
			//cout << b[i] << " " << b[j] << " " << w[i] << " " << w[j] << endl;
			return 0;
		}
		else 
			return 1;
	}
	else {
		if (belong(b[i], w[i], w[j])) 
			return 2;
		else 
			return 3;
	}
}

bool dps(int v) {
	bool ret = 1;
	if (col[v] == 1)
		return 0;
	col[v] = 1;
	for (auto to : pp[v]) {
		ret &= dps(to);
	}
	col[v] = 2;
	return ret;
}

void solve() {
	cleaning();
	cin >> n;
	ln = log2(n) + 1;
	bool flag = true;
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		if (x != i || y != i + 1)
			flag = false;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	cin >> m;
	for (int i = 1; i <= m; i++) {
		cin >> b[i] >> w[i];
	}
	if (false) {
		for (int i = 1; i <= m; i++) {
			sb[i] = pii(b[i], i);
			sw[i] = pii(w[i], i);
		}
		sort(sb + 1, sb + m + 1);
		sort(sw + 1, sw + m + 1);
		for (int i = 1; i <= m; i++) {
			if (sb[i].second != sw[i].second) {
				cout << "No\n";
				return;
			}
		}
		cout << "Yes\n";
	}
	else {
		p[1] = 1;
		for (int i = 0; i < ln; i++) {
			d[1][i] = 1;
		}
		dfs(1);
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				if (j == i) continue;
				int com = compare(i, j);
				if (com == 0) {
					cout << "No\n";
					return;
				}
				else if (com == 1) {
					pp[i].insert(j);
				}
				else if (com == 2) {
					pp[j].insert(i);
				}
			}
		}
		//cout << "imbluedabudidabudaidabudidabudaidabudidabudai\n";
		if (dps(1))
			cout << "Yes\n";
		else
			cout << "No\n";
	}
}

int main() {
	int t = 1;
	cin >> t;
	while (t--)
		solve();
	return 0;
}

/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
4
1 5
2 6
3 7
4 8

*/

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'void solve()':
jail.cpp:123:7: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
  123 |  bool flag = true;
      |       ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...