| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1053584 |
2024-08-11T13:51:34 Z |
j_vdd16 |
Jail (JOI22_jail) |
C++17 |
|
12 ms |
484 KB |
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
int n, m;
vvi adj;
vi depth;
vi parent;
vii inOut;
int counter;
void dfs(int node, int p, int d) {
depth[node] = d;
inOut[node].first = counter++;
for (int child : adj[node]) {
if (child == p) continue;
parent[child] = node;
dfs(child, node, d + 1);
}
inOut[node].second = counter++;
}
constexpr int POW = 20;
vi lift[POW];
bool isAncestor(int a, int b) {
return inOut[a].first <= inOut[b].first && inOut[b].first <= inOut[a].second;
}
bool isBetween(int node, int a, int b) {
return isAncestor(a, node) && isAncestor(node, b);
}
int getLCA(int a, int b) {
if (depth[a] < depth[b]) swap(a, b);
int todo = depth[a] - depth[b];
loop(pow, POW) {
if (todo & (1 << pow)) {
a = lift[pow][a];
}
}
if (a == b) return a;
for (int pow = POW - 1; pow >= 0; pow--) {
if (lift[pow][a] == lift[pow][a]) continue;
a = lift[pow][a];
b = lift[pow][b];
}
return lift[0][a];
}
bool isOnSimplePath(int node, int a, int b) {
int lca = getLCA(a, b);
return isBetween(node, lca, a) || isBetween(node, lca, b);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
/*
1
7
1 2
2 3
3 4
4 5
5 6
6 7
3
*/
/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
3
3 1
5 3
4 2
*/
int q;
cin >> q;
while (q--) {
cin >> n;
counter = 0;
adj = vvi(n);
depth = vi(n);
parent = vi(n);
inOut = vii(n);
loop(i, n - 1) {
int a, b;
cin >> a >> b;
a--; b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
dfs(0, -1, 0);
loop(i, POW) {
lift[i] = vi(n);
}
loop(i, n) lift[0][i] = parent[i];
lift[0][0] = 0;
for (int pow = 1; pow < POW; pow++) {
loop(j, n) {
int next = lift[pow - 1][j];
lift[pow][j] = lift[pow - 1][next];
}
}
vii routes;
cin >> m;
loop(i, m) {
int s, t;
cin >> s >> t;
s--; t--;
routes.push_back({s, t});
}
sort(all(routes));
bool containSuccess = true;
vi inDegree(m);
vvi out(m);
loop(i, m) {
auto [s1, t1] = routes[i];
loop(j, i) {
auto [s2, t2] = routes[j];
if (isOnSimplePath(t2, s1, t1)) {
out[j].push_back(i);
inDegree[i]++;
if (isOnSimplePath(s2, s1, t1)) containSuccess = false;
}
if (isOnSimplePath(t1, s2, t2)) {
out[i].push_back(j);
inDegree[j]++;
if (isOnSimplePath(s1, s2, t2)) containSuccess = false;
}
}
}
stack<int> startingPoints;
loop(i, m) {
if (inDegree[i] == 0) startingPoints.push(i);
}
int count = 0;
while (startingPoints.size()) {
int node = startingPoints.top();
startingPoints.pop();
count++;
for (int child : out[node]) {
inDegree[child]--;
if (inDegree[child] == 0) startingPoints.push(child);
}
}
bool testSuccess = true;
int prev = 0;
for (auto [s, t] : routes) {
if (t < prev) {
testSuccess = false;
}
prev = t;
}
if (testSuccess) {
cerr << "Yes (first subtask only)" << endl;
}
else {
cerr << "No (first subtask only)" << endl;
}
if (!containSuccess || count != m) {
cout << "No" << endl;
}
else {
cout << "Yes" << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
484 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
8 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
