Submission #966061

#	Time	Username	Problem	Language	Result	Execution time	Memory
966061		shenfe1	Jail (JOI22_jail)	C++17	72 / 100	5042 ms	854160 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;

  for(int i=1;i<=L;i++){
    up[v][i]=up[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){
  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){
  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*30];

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: 12 / 12
• Subtask 6: 11 / 11
• Subtask 7: 0 / 23