| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1116677 |
2024-11-22T07:46:16 Z |
Zero_OP |
Jail (JOI22_jail) |
C++14 |
|
2 ms |
592 KB |
#include <bits/stdc++.h>
using namespace std;
#define dbg(x) "[" #x " = " << (x) << "]"
bool cycle_detection(vector<vector<int>>& adj){
int N = (int)adj.size();
vector<int> vis(N);
function<bool(int)> dfs = [&](int u){
vis[u] = 1;
for(auto v : adj[u]){
if(!vis[v]){
if(dfs(v)) return true;
} else if(vis[v] == 1){
return true;
}
}
vis[u] = 2;
return false;
};
for(int i = 0; i < N; ++i){
if(!vis[i] && dfs(i)) return true;
}
return false;
}
struct path_decomposition_tree{
int N, timerHLD, num;
vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
vector<vector<int>> adj;
vector<pair<int, int>> edges;
path_decomposition_tree(int N) :
timerHLD(0), num(0), N(N), depth(N), sz(N), tin(N, -1), tout(N, -1), par(N), head(N), adj(N), edges(), idx(N),
ln(4 * N, -1), rn(4 * N, -1) {}
void add_edge(int u, int v){
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
void dfs_sz(int u){
sz[u] = 1;
for(auto& v : adj[u]){
adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
depth[v] = depth[u] + 1;
par[v] = u;
dfs_sz(v);
if(sz[adj[u][0]] < sz[v]) swap(adj[u][0], v);
sz[u] += sz[v];
}
}
int dfs_hld(int u, int hd){
head[u] = hd;
tin[u] = timerHLD++;
for(auto v : adj[u]){
if(v == adj[u][0]) dfs_hld(v, hd);
else dfs_hld(v, v);
}
tout[u] = timerHLD - 1;
}
int build(int l, int r){
if(l == r){
idx[l] = num++;
return idx[l];
} else{
int mid = l + r >> 1, cur = num++;
ln[cur] = build(l, mid);
rn[cur] = build(mid + 1, r);
edges.emplace_back(cur, ln[cur]);
edges.emplace_back(cur, rn[cur]);
return cur;
}
}
void preprocess(int rt){
dfs_sz(rt);
dfs_hld(rt, rt);
assert(timerHLD == N);
build(0, N - 1);
}
int auxiliary_nodes(){ return num; }
bool in_subtree(int u, int v){ return tin[u] <= tin[v] && tout[v] <= tout[u]; }
void query_auxiliary_nodes(int cur, int l, int r, int u, int v, vector<int>& ans){
if(u <= l && r <= v){
ans.emplace_back(cur);
} else{
int mid = l + r >> 1;
if(u <= mid) query_auxiliary_nodes(ln[cur], l, mid, u, v, ans);
if(mid < v) query_auxiliary_nodes(rn[cur], mid + 1, r, u, v, ans);
}
}
vector<int> query(int u, int v){ //ignore u, v
vector<int> cur;
if(tin[u] > tin[v]) swap(u, v);
if(in_subtree(u, v)){
v = par[v];
while(head[u] != head[v]){
if(depth[head[u]] < depth[head[v]]) swap(u, v);
query_auxiliary_nodes(0, 0, N - 1, tin[head[u]], tin[u], cur);
u = par[head[u]];
}
if(tin[u] < tin[v]) query_auxiliary_nodes(0, 0, N - 1, tin[u] + 1, tin[v], cur);
return cur;
} else{
u = par[u];
v = par[v];
}
while(head[u] != head[v]){
if(depth[head[u]] < depth[head[v]]) swap(u, v);
query_auxiliary_nodes(0, 0, N - 1, tin[head[u]], tin[u], cur);
u = par[head[u]];
}
if(tin[u] > tin[v]) swap(u, v);
query_auxiliary_nodes(0, 0, N - 1, tin[u], tin[v], cur);
return cur;
}
};
void testcase(){
int N;
cin >> N;
path_decomposition_tree tr(N);
for(int i = 1; i < N; ++i){
int u, v;
cin >> u >> v;
--u, --v;
tr.add_edge(u, v);
}
int M;
cin >> M;
tr.preprocess(0);
int offset = tr.auxiliary_nodes();
int nodes = 2 * offset + M;
vector<vector<int>> G(nodes);
for(auto [u, v] : tr.edges){
G[u].emplace_back(v); //for T
G[v + offset].emplace_back(u + offset); //for S
}
for(int i = 0; i < M; ++i){
int s, t;
cin >> s >> t;
--s, --t;
int loc = 2 * offset + i;
vector<int> compress_nodes = tr.query(s, t); //auxiliary nodes without s, t
for(auto it : compress_nodes){
G[loc].emplace_back(it);
G[it + offset].emplace_back(loc);
}
int pS = tr.idx[s];
G[loc].emplace_back(pS + offset);
G[loc].emplace_back(pS);
int pT = tr.idx[t];
G[pT].emplace_back(loc);
G[pT + offset].emplace_back(loc);
}
cout << (cycle_detection(G) ? "No\n" : "Yes\n");
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while(T--) testcase();
return 0;
}
Compilation message
jail.cpp: In constructor 'path_decomposition_tree::path_decomposition_tree(int)':
jail.cpp:31:22: warning: 'path_decomposition_tree::num' will be initialized after [-Wreorder]
31 | int N, timerHLD, num;
| ^~~
jail.cpp:31:9: warning: 'int path_decomposition_tree::N' [-Wreorder]
31 | int N, timerHLD, num;
| ^
jail.cpp:36:5: warning: when initialized here [-Wreorder]
36 | path_decomposition_tree(int N) :
| ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:32:38: warning: 'path_decomposition_tree::tout' will be initialized after [-Wreorder]
32 | vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
| ^~~~
jail.cpp:32:17: warning: 'std::vector<int> path_decomposition_tree::par' [-Wreorder]
32 | vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
| ^~~
jail.cpp:36:5: warning: when initialized here [-Wreorder]
36 | path_decomposition_tree(int N) :
| ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp:34:28: warning: 'path_decomposition_tree::edges' will be initialized after [-Wreorder]
34 | vector<pair<int, int>> edges;
| ^~~~~
jail.cpp:32:50: warning: 'std::vector<int> path_decomposition_tree::idx' [-Wreorder]
32 | vector<int> par, depth, sz, tin, tout, head, idx, ln, rn;
| ^~~
jail.cpp:36:5: warning: when initialized here [-Wreorder]
36 | path_decomposition_tree(int N) :
| ^~~~~~~~~~~~~~~~~~~~~~~
jail.cpp: In member function 'int path_decomposition_tree::dfs_hld(int, int)':
jail.cpp:65:5: warning: no return statement in function returning non-void [-Wreturn-type]
65 | }
| ^
jail.cpp: In member function 'int path_decomposition_tree::build(int, int)':
jail.cpp:72:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = l + r >> 1, cur = num++;
| ~~^~~
jail.cpp: In member function 'void path_decomposition_tree::query_auxiliary_nodes(int, int, int, int, int, std::vector<int>&)':
jail.cpp:96:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int mid = l + r >> 1;
| ~~^~~
jail.cpp: In function 'void testcase()':
jail.cpp:154:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
154 | for(auto [u, v] : tr.edges){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
592 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
