| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 695312 |
2023-02-05T01:09:34 Z |
GusterGoose27 |
Jail (JOI22_jail) |
C++11 |
|
2 ms |
3028 KB |
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 12e4;
const int BITS = 17;
vector<int> edges[MAXN];
bool adj[500][500];
int n, m;
pii queries[MAXN];
int lca[MAXN][BITS];
int depth[MAXN];
vector<int> order;
bool vis[500];
class query {
public:
int l, r;
bool f;
query(int l, int r, bool f) : l(l), r(r), f(f) {}
};
bool operator<(query &a, query &b) {
return (a.l == b.l) ? (a.r > b.r) : (a.l < b.l);
}
void dfs(int cur = 0, int p = -1) {
for (int nxt: edges[cur]) {
if (nxt == p) continue;
depth[nxt] = depth[cur]+1;
lca[nxt][0] = cur;
dfs(nxt, cur);
}
}
int get_lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y);
int diff = depth[x]-depth[y];
int p = 0;
while (diff) {
if (diff & 1) x = lca[x][p];
diff /= 2;
p++;
}
if (x == y) return x;
for (int i = 16; i >= 0; i--) {
if (lca[x][i] != lca[y][i]) {
x = lca[x][i];
y = lca[y][i];
}
}
return lca[x][0];
}
int dist(int x, int y) {
return depth[x]+depth[y]-2*depth[get_lca(x, y)];
}
bool on_seg(int a, int b, int c) {
return dist(a, b) == dist(a, c)+dist(b, c);
}
void dfs2(int cur) {
vis[cur] = 1;
for (int i = 0; i < m; i++) {
if (!vis[i] && adj[cur][i]) dfs2(i);
}
order.push_back(cur);
}
int main() {
int t; cin >> t;
while (t--) {
bool s1 = 1;
cin >> n;
for (int i = 0; i < n; i++) edges[i].clear();
for (int i = 0; i < n-1; i++) {
int x, y; cin >> x >> y;
x--; y--;
edges[x].push_back(y);
edges[y].push_back(x);
if (y-x != 1) s1 = 0;
}
cin >> m;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
queries[i] = pii(x-1, y-1);
}
if (0) {
vector<query> sorted;
for (int i = 0; i < m; i++) {
if (queries[i].first > queries[i].second) sorted.push_back(query(queries[i].second, queries[i].first, 1));
else sorted.push_back(query(queries[i].first, queries[i].second, 0));
}
sort(sorted.begin(), sorted.end());
int r[2];
r[0] = r[1] = -1;
bool ans = 1;
for (query q: sorted) {
if (r[q.f] >= q.r || r[!q.f] >= q.l) {
ans = 0;
break;
}
r[q.f] = q.r;
}
if (ans) {
cout << "Yes\n";
}
else cout << "No\n";
}
else if (m <= 500) {
dfs();
for (int i = 1; i < BITS; i++) {
for (int j = 0; j < n; j++) {
lca[j][i] = lca[lca[j][i-1]][i-1];
}
}
for (int i = 0; i < m; i++) fill(adj[i], adj[i]+m, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
if (i == j) continue;
if (on_seg(queries[i].first, queries[i].second, queries[j].first) || on_seg(queries[j].first, queries[j].second, queries[i].second)) adj[i][j] = 1;
}
}
fill(vis, vis+m, 0);
order.clear();
for (int i = 0; i < m; i++) {
if (!vis[i]) dfs2(i);
}
bool ans = 1;
for (int i = 0; i < m && ans; i++) {
for (int j = i+1; j < m && ans; j++) {
if (adj[order[i]][order[j]]) ans = 0;
}
}
if (ans) cout << "YES\n";
else cout << "NO\n";
}
else {
srand(0);
if (rand()%2) cout << "YES\n";
else cout << "NO\n";
}
}
}
Compilation message
jail.cpp: In function 'int main()':
jail.cpp:77:8: warning: variable 's1' set but not used [-Wunused-but-set-variable]
77 | bool s1 = 1;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
