oj.uz

답안 #887647

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887647 2023-12-14T23:43:19 Z TAhmed33 Jail (JOI22_jail) C++
0 / 100
 7 ms 6832 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 120025;
vector <int> adj[MAXN];
vector <int> adj2[501];
int n, m;
int l[501], r[501], deg[501];
vector <int> dd[MAXN];
vector <int> ls[501];
bool dfs (int pos, int par, int c) {
	if (pos == r[c]) {
		dd[pos].push_back(c);
		ls[c].push_back(pos);
		return 1;
	}
	bool f = 0;
	for (auto i : adj[pos]) {
		if (i != par) {
			f |= dfs(i, pos, c);
		}
	}
	if (f) {
		dd[pos].push_back(c);
		ls[c].push_back(pos);
	}
	return f;
}
int mx1[MAXN], mx2[MAXN];
void solve () {
	cin >> m;
	vector <pair <int, int>> gg, ff, xx;
	for (int i = 0; i < m; i++) {
		int l, r;
		cin >> l >> r;
		if (r < l) ff.push_back({r, l}), swap(l, r);
		else gg.push_back({l, r});
		xx.push_back({l, r});
	}
	for (int i = 0; i <= n; i++) mx1[i] = mx2[i] = 0;
	sort(xx.begin(), xx.end(), [] (pair <int, int> a, pair <int, int> b) {
		return a.first == b.first ? a.second > b.second : a.first < b.first;
	});
	reverse(xx.begin(), xx.end());
	set <int> dd;
	bool flag = 0;
	for (auto [j, k] : xx) {
		//cout << j << " " << k << '\n';
		if (!dd.empty()) flag |= *(dd.begin()) <= k;
		dd.insert(k);
	}
	if (flag) {
		cout << "No\n";
		return;
	}
	for (auto [j, k] : gg) {
		mx1[j] = max(mx1[j], k);
	}
	for (auto [j, k] : ff) {
		mx2[j] = max(mx2[j], k);
	}
	for (int i = n - 1; i >= 1; i--) {
		mx1[i] = max(mx1[i], mx1[i + 1]);
		mx2[i] = max(mx2[i], mx2[i + 1]);
	}
	for (auto [j, k] : gg) {
		flag |= mx2[j] >= k;
	}
	for (auto [j, k] : ff) {
		flag |= mx1[j] >= k;
	}
	cout << (flag ? "No\n" : "Yes\n");
}
int main () {
	ios::sync_with_stdio(0); cin.tie(0);
	int t = 1; cin >> t;
	while (t--) {
		cin >> n;
		bool flag6 = 1;
		for (int i = 1; i <= n; i++) {
			adj[i].clear();
			dd[i].clear();
		}
		for (int i = 1; i < n; i++) {
			int a, b;
			cin >> a >> b;
			flag6 &= a == i && b == i + 1;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		if (flag6) {
			solve();
			continue;
		}
		cin >> m;
		for (int i = 1; i <= m; i++) {
			deg[i] = 0; adj2[i].clear(); ls[i].clear();
		}
		for (int i = 1; i <= m; i++) {
			cin >> l[i] >> r[i];
			dfs(l[i], -1, i);
		}
		for (int i = 1; i <= n; i++) sort(dd[i].begin(), dd[i].end());
		bool flag3 = 0;
		for (int i = 1; i <= m; i++) {
			set <int> y;
			for (auto j : dd[l[i]]) y.insert(j);
			bool u2 = 0;
			for (auto j : dd[r[i]]) u2 |= y.count(j) && j != i;
			flag3 |= u2;
			u2 = 0;
			for (auto j : dd[l[i]]) if (j != i) u2 |= binary_search(dd[l[j]].begin(), dd[l[j]].end(), i);
			for (auto j : dd[r[i]]) if (j != i) u2 |= binary_search(dd[r[j]].begin(), dd[r[j]].end(), i);
			flag3 |= u2;
		}
		if (flag3) {
			cout << "No\n";
			continue;	
		}
		for (int i = 1; i <= m; i++) sort(ls[i].begin(), ls[i].end());
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= m; j++) {
				if (i == j) continue;
				bool flag = 0;
				flag |= binary_search(ls[i].begin(), ls[i].end(), l[j]);
				flag |= binary_search(ls[j].begin(), ls[j].end(), r[i]);
				if (flag) adj2[i].push_back(j);
			}
		}
		for (int i = 1; i <= m; i++) {
			for (auto j : adj2[i]) {
				deg[j]++;
			}
		}
		vector <int> d;
		queue <int> cur;
		for (int i = 1; i <= m; i++) {
			if (deg[i] == 0) {
				cur.push(i);
			}
		}
		while (!cur.empty()) {
			auto j = cur.front();
			cur.pop();
			d.push_back(j);
			for (auto z : adj2[j]) {
				deg[z]--;
				if (deg[z] == 0) cur.push(z);
			}
		}
		if ((int)d.size() != m) {
			cout << "No\n";
		} else {
			cout << "Yes\n";
		}
	}
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:46:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |  for (auto [j, k] : xx) {
      |            ^
jail.cpp:55:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   55 |  for (auto [j, k] : gg) {
      |            ^
jail.cpp:58:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   58 |  for (auto [j, k] : ff) {
      |            ^
jail.cpp:65:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |  for (auto [j, k] : gg) {
      |            ^
jail.cpp:68:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   68 |  for (auto [j, k] : ff) {
      |            ^

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Incorrect 7 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 1 ms 6748 KB Output is correct
5 Incorrect 4 ms 6832 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 6748 KB Output is correct
2 Correct 1 ms 6748 KB Output is correct
3 Correct 1 ms 6748 KB Output is correct
4 Incorrect 7 ms 6748 KB Output isn't correct
5 Halted 0 ms 0 KB -