| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 725022 |
2023-04-16T13:06:11 Z |
berr |
Jail (JOI22_jail) |
C++17 |
|
23 ms |
12568 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 2e4 + 37;
vector<int> adj[N], adj2[N], adj3[N], s(N), e(N), ti(N), to(N), vis(N), de(N), qe(N, -1), qs(N, -1);
int par[N][18], cnt, flag, taa=0;
bool ia(int x, int y){
return ti[x] <= ti[y] && to[x] >= to[y];
}
int d(int x, int y){
if(x == y) return 0;
int sum = 0;
if(ia(x, y)) swap(x, y);
for (int i = 4; i >= 0; i--){
if(!ia(par[x][i], y)){
x = par[x][i];
sum += 1<<i;
}
}
sum++;
x=par[x][0];
swap(x, y);
sum+=de[x]-de[y];
return sum;
}
bool c(int x, int y){
if(x==y || x==-1 || y==-1) return 0;
if( (d(s[x], e[x]) == (d(s[x], e[y])+ d(e[y], e[x])))) return 1;
swap(x, y);
return (d(s[x], e[x]) == (d(s[x], s[y])+ d(s[y], e[x])));
}
bool c2(int x, int y){
if(x==y || x==-1 || y==-1 ) return 0;
if(d(s[x], e[x]) == d(s[x], s[y])+ d(s[y], e[y]) + d(e[y], e[x])) return 1;
if(d(s[x], e[x]) == d(s[x], e[y])+ d(e[y], s[y]) + d(s[y], e[x])) return 1;
return 0;
}
void dfs(int v, int p){
par[v][0] = p;
de[v]=de[p]+1;
ti[v] = cnt++;
for (auto i: adj[v]){
if (i == p) continue;
dfs(i, v);
}
to[v] = cnt++;
}
void dfs2(int v, int z){
vis[v] = z;
for (auto i: adj2[v]){
if (vis[i]==z) flag = 0;
else if(vis[i]<z) dfs2(i, z);
}
vis[v]=z+1;
}
void ssolve(int n, int m){
taa=1;
for(int i=0;i<m; i++){
int x=s[i], y=e[i];
while(!ia(x, y)){
int l=qs[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
l=qe[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
x=par[x][0];
}
int l=qs[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
l=qe[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
while(!ia(y, x)){
int l=qs[y];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
l=qe[y];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
y=par[y][0];
}
}
for(int i = 0; i < n; i++){
if(vis[i]==0) dfs2(i, n*i+1);
}
if(flag) cout<<"Yes\n";
else cout<<"No\n";
for (int i = 0; i < n; i++){
adj[i].clear();
adj2[i].clear();
vis[i] = 0;
qs[i]=qe[i]=-1;
}
taa=0;
}
void solve(){
int n; cin >> n;
cnt = 0;
for (int i = 1; i < n; i++){
int x, y; cin >> x >> y;
x--; y--;
adj[x].push_back(y);
adj[y].push_back(x);
}
de[0]=-1;
dfs(0, 0);
for (int i = 1; i < 5; i++){
for(int l = 0; l < n; l++){
par[l][i] = par[par[l][i-1]][i-1];
}
}
flag = 1;
int m; cin >> m;
for (int i = 0; i < m; i++){
cin >> s[i] >> e[i];
s[i]--; e[i]--;
qs[s[i]]=i;
qe[e[i]]=i;
}
for(int i=0;i<m; i++){
int x=s[i], y=e[i];
while(!ia(x, y)){
int l=qs[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
l=qe[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
x=par[x][0];
}
int l=qs[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
l=qe[x];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
while(!ia(y, x)){
int l=qs[y];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
l=qe[y];
if (c(i, l)) adj2[i].push_back(l);
if(c2(i, l)) flag = 0;
y=par[y][0];
}
}
for(int i = 0; i < n; i++){
if(vis[i]==0) dfs2(i, n*i+1);
}
if(flag) cout<<"Yes\n";
else cout<<"No\n";
for (int i = 0; i < n; i++){
adj[i].clear();
adj2[i].clear();
vis[i] = 0;
qs[i]=qe[i]=-1;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int t; cin>>t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
12500 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
12500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
12500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
12500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 3 |
Incorrect |
7 ms |
12500 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
7 ms |
12560 KB |
Output is correct |
| 3 |
Correct |
8 ms |
12500 KB |
Output is correct |
| 4 |
Correct |
7 ms |
12528 KB |
Output is correct |
| 5 |
Correct |
23 ms |
12480 KB |
Output is correct |
| 6 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 7 |
Correct |
9 ms |
12500 KB |
Output is correct |
| 8 |
Correct |
9 ms |
12500 KB |
Output is correct |
| 9 |
Correct |
8 ms |
12500 KB |
Output is correct |
| 10 |
Incorrect |
8 ms |
12568 KB |
Output isn't correct |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
12500 KB |
Output is correct |
| 2 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 3 |
Correct |
6 ms |
12500 KB |
Output is correct |
| 4 |
Incorrect |
14 ms |
12500 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
