Submission #966053

#	Time	Username	Problem	Language	Result	Execution time	Memory
966053		shenfe1	Jail (JOI22_jail)	C++17	49 / 100	2304 ms	1009772 KiB

jail

#include <bits/stdc++.h>

#pragma optimize("Ofast")
#pragma target("avx2")

using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define pf push_front
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define mem(a,i) memset(a,i,sizeof(a))
#define sz(s) (int)s.size()
#define y1 yy
#define ppb pop_back
#define lb lower_bound
#define ub upper_bound
#define gcd(a,b) __gcd(a,b)
#define in insert
// #define int ll
#define ull unsigned ll

const int MAX=5e5+15;
const int B=331;
const int maxB=1000;
const int N=104;
const int block=450;
const ll inf=1e13;  
const int mod=1e9+7;
const int mod1=1e9+9;
const ld eps=1e-9;

int dx[8]={1,0,-1,0,1,-1,-1,1};
int dy[8]={0,1,0,-1,1,-1,1,-1};

int binpow(int a,int n){
  if(!n)return 1;
  if(n%2==1)return a*binpow(a,n-1)%mod;
  int k=binpow(a,n/2);
  return k*k%mod;
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m;
int cur;
vector<int> g[MAX];
vector<int> g1[MAX*30];
int up[MAX][20];
int in[MAX][20],out[MAX][20];
int s[MAX],t[MAX];
vector<int> pos[MAX];

int tin[MAX],tout[MAX],timer;
int d[MAX];

const int L=19;

void add(int x,int y){
  g1[x].pb(y);
  // cout<<x<<" "<<y<<"\n";
}

void dfs(int v,int p=1){
  tin[v]=++timer;
  up[v][0]=p;
  in[v][0]=++cur;
  out[v][0]=++cur;

  // cout<<"!!!! "<<v<<"\n";

  // for(int x:pos[v]){
  //   if(x>0){
  //     add(in[v][0],x);
  //   }
  //   else{
  //     add(-x,out[v][0]);
  //   }
  // }


  for(int i=1;i<=L;i++){
    in[v][i]=++cur;
    out[v][i]=++cur;
    up[v][i]=up[up[v][i-1]][i-1];
    add(out[v][i-1],out[v][i]);
    add(out[up[v][i-1]][i-1],out[v][i]);
    add(in[v][i],in[v][i-1]);
    add(in[v][i],in[up[v][i-1]][i-1]);
  }

  for(auto to:g[v]){
    if(to==p)continue;
    d[to]=d[v]+1;
    dfs(to,v);
  }
  tout[v]=timer;
}

bool par(int u,int v){
  return (tin[u]<=tin[v]&&tout[v]<=tout[u]);
}

void addin(int x,int y,int z){
  // for(int i=L;i>=0;i--){
  //   if(d[up[x][i]]>d[y]){
  //     // cout<<x<<" "<<i<<" "<<in[x][i]<<"\n";
  //     add(z,in[x][i]);
  //     x=up[x][i];
  //   }
  // }

  while(d[x]>=d[y]){
    for(int f:pos[x]){
      if(f>0&&f!=z)add(z,f);
    }
    if(x==1)break;
    x=up[x][0];
  }
}

void addout(int x,int y,int z){
  // for(int i=L;i>=0;i--){
  //   if(d[up[x][i]]>d[y]){
  //     add(out[x][i],z);
  //     x=up[x][i];
  //   }
  // }

  while(d[x]>=d[y]){
    for(int f:pos[x]){
      if(f<0&&f!=-z)add(-f,z);
    }
    if(x==1)break;
    x=up[x][0];
  }
}

int lca(int x,int y){
  if(par(x,y))return x;
  if(par(y,x))return y;
  for(int i=L;i>=0;i--){
    if(!par(up[x][i],y)){
      x=up[x][i];
    }
  }
  return up[x][0];
}

bool bad;
int use[MAX];

void dfs1(int v){
  use[v]=1;
  for(auto to:g1[v]){
    if(!use[to]){
      // cout<<v<<" "<<to<<"\n";
      dfs1(to);
    }
    else if(use[to]==1){
      bad=1;
      // cout<<v<<" "<<to<<"\n";
    }
  }
  use[v]=2;
}

void solve(){
  cin>>n;
  
  bad=0;
  timer=0;
  for(int i=1;i<=cur;i++){
    g1[i].clear();
    use[i]=0;
  }
  for(int i=1;i<=n;i++){
    g[i].clear();
    pos[i].clear();
  }

  for(int i=1;i<n;i++){
    int x,y;
    cin>>x>>y;
    g[x].pb(y);
    g[y].pb(x);
  }

  cin>>m;

  for(int i=1;i<=m;i++){
    cin>>s[i]>>t[i];
    pos[s[i]].pb(i);
    pos[t[i]].pb(-i);
  }
  cur=m;
  dfs(1);
  // cout<<"\n";
  for(int i=1;i<=m;i++){
    int l=lca(s[i],t[i]);
    // cout<<l<<"\n";
    addin(s[i],l,i);
    addin(t[i],l,i);

    addout(s[i],l,i);
    addout(t[i],l,i);
  }
  // return;
  for(int i=1;i<=cur;i++){
    if(!use[i])dfs1(i);
  }
  if(bad)cout<<"No\n";
  else cout<<"Yes\n";
}

signed main(){
  // freopen("triangles.in","r",stdin);
  // freopen("triangles.out","w",stdout);
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  // prec();
  int t=1;
  cin>>t;
  while(t--)solve();
}

Compilation message (stderr)

jail.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    3 | #pragma optimize("Ofast")
      | 
jail.cpp:4: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    4 | #pragma target("avx2")
      |

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23