| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 887647 |
2023-12-14T23:43:19 Z |
TAhmed33 |
Jail (JOI22_jail) |
C++ |
|
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) {
| ^
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
