| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1053552 |
2024-08-11T13:09:48 Z |
j_vdd16 |
Jail (JOI22_jail) |
C++17 |
|
1 ms |
348 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 int long long
#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;
typedef uint64_t u64;
typedef int64_t i64;
int n, m;
vvi adj;
vi depth;
vi parent;
void dfs(int node, int p, int d) {
depth[node] = d;
for (int child : adj[node]) {
if (child == p) continue;
parent[child] = node;
dfs(child, node, d + 1);
}
}
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 3
4 2
2 5
*/
/*
1
8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
2
1 5
2 3
*/
int q;
cin >> q;
constexpr int POW = 20;
while (q--) {
cin >> n;
adj = vvi(n);
depth = vi(n);
parent = vi(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);
vi lift[POW] = {};
vvi endPointLift[POW] = {};
vvi startPointLift[POW] = {};
loop(i, POW) {
lift[i] = vi(n);
endPointLift[i] = vvi(n);
startPointLift[i] = vvi(n);
}
loop(i, n) lift[0][i] = parent[i];
lift[0][0] = 0;
vii routes;
cin >> m;
loop(i, m) {
int s, t;
cin >> s >> t;
s--; t--;
routes.push_back({s, t});
endPointLift[0][t].push_back(i);
startPointLift[0][s].push_back(i);
}
for (int pow = 1; pow < POW; pow++) {
loop(j, n) {
endPointLift[pow][j] = endPointLift[pow - 1][j];
startPointLift[pow][j] = startPointLift[pow - 1][j];
int next = lift[pow - 1][j];
lift[pow][j] = lift[pow - 1][next];
//if (next == 0) continue;
for (int x : endPointLift[pow - 1][next]) {
endPointLift[pow][j].push_back(x);
}
for (int x : startPointLift[pow - 1][next]) {
startPointLift[pow][j].push_back(x);
}
}
}
bool containSuccess = true;
vi inDegree(m);
vector<set<int>> out(m);
loop(i, m) {
auto [s, t] = routes[i];
vi endPointsOnRoute;
set<int> startPointsOnRoute;
if (depth[s] < depth[t]) swap(s, t);
int todo = depth[s] - depth[t];
int total = 0;
loop(pow, POW) {
if (todo & (1 << pow)) {
for (int x : endPointLift[pow][s]) endPointsOnRoute.push_back(x);
for (int x : startPointLift[pow][s]) startPointsOnRoute.insert(x);
total += (1 << pow);
s = lift[pow][s];
}
}
for (int pow = POW - 1; pow >= 0; pow--) {
if (lift[pow][s] == lift[pow][t]) continue;
for (int x : endPointLift[pow][s]) endPointsOnRoute.push_back(x);
for (int x : endPointLift[pow][t]) endPointsOnRoute.push_back(x);
for (int x : startPointLift[pow][s]) startPointsOnRoute.insert(x);
for (int x : startPointLift[pow][t]) startPointsOnRoute.insert(x);
total += 2 * (1 << pow);
s = lift[pow][s];
t = lift[pow][t];
}
if (s == t) {
total++;
for (int x : endPointLift[0][s]) endPointsOnRoute.push_back(x);
for (int x : startPointLift[0][s]) startPointsOnRoute.insert(x);
}
else {
total += 3;
for (int x : endPointLift[1][s]) endPointsOnRoute.push_back(x);
for (int x : endPointLift[0][t]) endPointsOnRoute.push_back(x);
for (int x : startPointLift[1][s]) startPointsOnRoute.insert(x);
for (int x : startPointLift[0][t]) startPointsOnRoute.insert(x);
}
cerr << "I = " << i << "(" << total << "): ";
for (int x : endPointsOnRoute) {
if (x == i) continue;
cerr << x << ' ';
if (startPointsOnRoute.count(i)) containSuccess = false;
inDegree[x]++;
out[i].insert(x);
}
cerr << endl;
}
if (!containSuccess) {
cout << "No" << endl;
continue;
}
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 success = true;
sort(all(routes));
int prev = 0;
for (auto [s, t] : routes) {
if (t < prev) {
success = false;
}
prev = t;
}
if (/*count == m*/success) {
cerr << "Yes" << endl;
}
else {
cerr << "No" << endl;
}
if (count == m) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
