| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 891067 |
2023-12-22T07:15:57 Z |
vjudge1 |
Jail (JOI22_jail) |
C++17 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 120000;
void solve(){
int n;cin >> n;
vector< vector<pair<int, int> > > g(n+1);
vector<int> edge1(n+1, 0), edge2(n+1, 0);
vector<int> par_index(n+1, 0);
for(int i = 1;i < n; i++){
int a, b; cin >> a >> b;
g[a].push_back({b, i});
g[b].push_back({a, i});
}
int q; cin >> q;
vector< pair<int, int> > query(q);
for(int i = 0;i < q; i++){
cin >> query[i].ff >> query[i].ss;
}
vector<int> sub(n + 1, 0), depth(n + 1, 0);
vector<int> tin(n + 1), tout(n + 1);
int timer = 1;
int up[n+1][18];
function<void(int, int)> dfs=[&](int v, int par){
tin[v] = timer++;
up[v][0] = par;
for(int j = 1;j < 18; j++){
up[v][j] = up[up[v][j-1]][j-1];
}
sub[v]+= 1;
for(auto [to, idx] : g[v]){
if(to == par) continue;
depth[to] = depth[v] + 1;
par_index[to] = idx;
dfs(to, v);
sub[v]+= sub[to];
}
tout[v] = timer;
};
dfs(1, 1);
auto lca = [&](int a, int b){
if(depth[a] > depth[b]) swap(a, b);
int k = depth[b] - depth[a];
for(int i = 0;i < 18; i++){
if(k & (1<<i)){
b = up[b][i];
}
}
if(a == b) return a;
for(int i = 17; i >= 0; i--){
if(up[a][i] != up[b][i]){
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
};
auto go = [&](int a, int p, int type){
int QQ = n+1;
while(a != p){
int idx = par_index[a];
if(type == 1) edge1[idx] = 1;
else edge2[idx] = 1;
a = up[a][0];
}
};
auto on_path=[&](int a, int p, int type){
while(a != p){
// cout << a << ' ';
int idx = par_index[a];
if(type == a) return 1;
a = up[a][0];
}
// cout << '\n';
if(p == type) return 1;
return 0;
};
for(int i = 0;i < q; i++){
for(int k = 1; k < n; k++){
edge1[k] = 0;
edge2[k] = 0;
}
auto [a, b] = query[i];
int lc = lca(a, b);
for(int j = 0;j < q; j++){
if(i == j) continue;
auto [a1, b1] = query[j];
int lc1 = lca(a1, b1);
//a1, lc1 -> b
//b1, lc1 -> a
if(on_path(b1, lc1, a) && a != lc1){
//cout << b1 << ' ' << lc1 << " = " << a << " -> ";
cout << "No";
return;
}
if(on_path(a1, lc1, b) && b != lc1){
// cout << a1 << " " << lc1 << " = " << b << " -> ";
cout << "No";
return;
}
}
}
for(int i = 0;i < q; i++){
for(int j = 0; j < q; j++){
if(i == j) continue;
auto [a, b] = query[i];
auto [a1, b1] = query[j];
int lc = lca(a, b);
int lc1 = lca(a1, b1);
for(int k = 1; k < n; k++) edge1[k] = 0;
go(a, lc, 1);
go(b, lc, 1);
int ok = 1;
while(a1 != lc1){
int idx = par_index[a1];
if(!edge1[idx]){
ok = 0;
break;
}
a1 = up[a1][0];
}
while(b1 != lc1){
int idx = par_index[b1];
if(!edge1[idx]){
ok = 0;
break;
}
b1 = up[b1][0];
}
if(ok){
cout << "No";
return;
}
}
}
cout << "Yes";
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int t; cin >> t;
while(t--){
solve();
cout << '\n';
}
return 0;
}
Compilation message
jail.cpp: In lambda function:
jail.cpp:68:7: warning: unused variable 'QQ' [-Wunused-variable]
68 | int QQ = n+1;
| ^~
jail.cpp: In lambda function:
jail.cpp:80:8: warning: unused variable 'idx' [-Wunused-variable]
80 | int idx = par_index[a];
| ^~~
jail.cpp: In function 'void solve()':
jail.cpp:95:7: warning: unused variable 'lc' [-Wunused-variable]
95 | int lc = lca(a, b);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 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 |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
