| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 648210 |
2022-10-05T17:30:37 Z |
victor_gao |
Jail (JOI22_jail) |
C++17 |
|
78 ms |
130312 KB |
//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define pii pair<int,int>
#define x first
#define y second
#define N 120015
#define C 21*120005
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
int n,m,ac[20][N],have1[20][N],have2[20][N],in[N],out[N],dep[N],t=0,st[N],ed[N];
int dfn[45*N],low[45*N],dft=0;
bool ins[45*N],ans=1;
stack<int>s;
vector<int>g[N],ng[45*N];
void dfs(int p,int lp){
ac[0][p]=lp;
in[p]=++t;
dep[p]=dep[lp]+1;
for (auto i:g[p]){
if (i!=lp) dfs(i,p);
}
out[p]=++t;
}
int Hash(int u,int p,int i){
return p*2*n+2*(u-1)+i;
}
void build(){
out[0]=1e9; in[0]=0;
for (int i=1;i<=19;i++){
for (int j=1;j<=n;j++){
ac[i][j]=ac[i-1][ac[i-1][j]];
have1[i][j]=have1[i-1][j]+have1[i-1][ac[i-1][j]];
if (have1[i-1][j]) ng[Hash(j,i-1,1)].push_back(Hash(j,i,1));
if (have1[i-1][ac[i-1][j]]) ng[Hash(ac[i-1][j],i-1,1)].push_back(Hash(j,i,1));
have2[i][j]=have2[i-1][j]+have2[i-1][ac[i-1][j]];
if (have2[i-1][j]) ng[Hash(j,i,2)].push_back(Hash(j,i-1,2));
if (have2[i-1][ac[i-1][j]]) ng[Hash(j,i,2)].push_back(Hash(ac[i-1][j],i-1,2));
}
}
}
bool check(int a,int b){
return in[a]<=in[b]&&out[a]>=out[b];
}
int LCA(int a,int b){
if (check(a,b)) return a;
if (check(b,a)) return b;
for (int i=19;i>=0;i--){
if (!check(ac[i][a],b)) a=ac[i][a];
}
return ac[0][a];
}
void add(int u,int up,int is){
if (up==0){
if (have1[0][u]&&have2[0][u])
ng[Hash(u,0,1)].push_back(Hash(u,0,2));
return;
}
int now=u;
for (int i=19;i>=0;i--){ // 遇不同
if (up&(1LL<<i)){
if (is==1){
ng[Hash(u,0,1)].push_back(Hash(now,i,2));
// cout<<"add diff: "<<Hash(u,0,1)<<" "<<Hash(now,i,2)<<" "<<u<<' '<<now<<'\n';
}
else {
ng[Hash(now,i,1)].push_back(Hash(u,0,2));
// cout<<"add diff: "<<Hash(now,i,1)<<" "<<Hash(u,0,2)<<" "<<now<<" "<<u<<'\n';
}
now=ac[i][now];
}
}
now=ac[0][u];
for (int i=19;i>=0;i--){
if (up&(1LL<<i)){
if (is==1){
ng[Hash(now,i,1)].push_back(Hash(u,0,1));
// cout<<"add same: "<<Hash(now,i,1)<<" "<<Hash(u,0,1)<<'\n';
}
else {
ng[Hash(u,0,2)].push_back(Hash(now,i,2));
// cout<<"add same: "<<Hash(u,0,2)<<" "<<Hash(now,i,2)<<'\n';
}
now=ac[i][now];
}
}
}
void tarjan(int p){
dfn[p]=low[p]=++dft;
s.push(p); ins[p]=1;
for (auto i:ng[p]){
if (!dfn[i]){
tarjan(i);
low[p]=min(low[p],low[i]);
}
else if (ins[i]&&dfn[i]<dfn[p])
low[p]=min(low[p],dfn[i]);
}
if (low[p]==dfn[p]){
int cnt=0;
vector<int>cycle;
for (int x=0;x!=p;s.pop()){
x=s.top();
cycle.push_back(x);
ins[x]=0; cnt++;
}
if (cnt>=2){
ans=0;
/*
cout<<"Find : ";
for (auto j:cycle)
cout<<j<<" ";
cout<<'\n';
*/
}
}
}
void reset(){
t=0; dft=0; ans=1;
while (!s.empty()) s.pop();
for (int i=0;i<=n+5;i++){
g[i].clear();
st[i]=0; ed[i]=0;
for (int j=0;j<=20;j++){
have1[j][i]=0; have2[j][i]=0;
ac[j][i]=0;
}
}
for (int i=0;i<=42*n;i++){
ins[i]=0; dfn[i]=0; low[i]=0;
dep[i]=0; out[i]=0; in[i]=0;
ng[i].clear();
}
}
signed main(){
fast
int q; cin>>q;
while (q--){
cin>>n;
reset();
for (int i=1;i<n;i++){
int a,b; cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
cin>>m;
for (int i=1;i<=m;i++){
cin>>st[i]>>ed[i];
have1[0][st[i]]=1;
have2[0][ed[i]]=1;
}
dfs(1,1);
build();
/*
for (int i=0;i<=5*n;i++){
if (!ng[i].empty()){
cout<<i<<" -> ";
for (auto j:ng[i])
cout<<j<<" ";
cout<<'\n';
}
}
*/
for (int i=1;i<=m;i++){
int a=st[i],b=ed[i];
int lca=LCA(a,b);
int dis=dep[a]-dep[lca];
add(a,dis,1);
dis=dep[b]-dep[lca];
add(b,dis,2);
ng[Hash(b,0,2)].push_back(Hash(a,0,1));
// cout<<"add: "<<Hash(b,0,2)<<" "<<Hash(a,0,1)<<'\n';
}
/*
for (int i=0;i<=5*n;i++){
if (!ng[i].empty()){
cout<<i<<" -> ";
for (auto j:ng[i])
cout<<j<<" ";
cout<<'\n';
}
}
*/
for (int i=1;i<42*n;i++){
if (!dfn[i]) tarjan(i);
}
if (ans) cout<<"Yes\n";
else cout<<"No\n";
}
}
Compilation message
jail.cpp: In function 'void reset()':
jail.cpp:131:24: warning: iteration 20 invokes undefined behavior [-Waggressive-loop-optimizations]
131 | have1[j][i]=0; have2[j][i]=0;
| ~~~~~~~~~~~^~
jail.cpp:130:23: note: within this loop
130 | for (int j=0;j<=20;j++){
| ~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
130292 KB |
Output is correct |
| 2 |
Incorrect |
67 ms |
130308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
130304 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
130252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
130304 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
130252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
130304 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
130252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
130304 KB |
Output is correct |
| 2 |
Incorrect |
74 ms |
130252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
130312 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
130252 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
78 ms |
130292 KB |
Output is correct |
| 2 |
Incorrect |
67 ms |
130308 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
