oj.uz

Submission #966166

# Submission time Handle Problem Language Result Execution time Memory
966166 2024-04-19T13:15:39 Z shenfe1 Jail (JOI22_jail) C++17
0 / 100
 2378 ms 1048576 KB 
#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());

const int L=20;
 
int n,m;
int cur;
vector<int> g[MAX];
vector<int> g1[MAX*L];
int up[MAX][L];
int in[MAX][L],out[MAX][L];
int s[MAX],t[MAX];
 
int tin[MAX],tout[MAX],timer;
int d[MAX];

 
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;


  // add(in[v][0],v);
  // add(v+n,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]);
}

bool bad;
int use[MAX*30];

void dfs1(int v,int p=-1){
  use[v]=1;
  for(auto to:g1[v]){
    if(to==p)continue;
    if(!use[to])dfs1(to,v);
    else if(use[to]==1)bad=1;
  }
  use[v]=2;
}
 
void ebash_tuda(int x,int y,int z,bool ok){
  // for(int i=L;i>=0;i--){
  //   if(!par(up[i][x],y)){
  //     add(z,in[x][i]);
  //     x=up[x][i];
  //   }
  // }
  while(!par(x,y)){
    add(z,x);
    x=up[x][0];
  }
  if(ok)add(z,x);
}

void ebash_ottuda(int x,int y,int z,bool ok){
  // for(int i=L;i>=0;i--){
  //   if(!par(up[i][x],y)){
  //     add(out[x][i],z);
  //     x=up[x][i];
  //   }
  // }
  while(!par(x,y)){
    add(x+n,z);
    x=up[x][0];
  }
  if(ok){
    add(x+n,z);
  }
}

void add(int x,int y,int z){
  // cout<<"!!! "<<x<<" "<<y<<" "<<z<<"\n";
  if(!par(x,y)){
    // cout<<1<<" "<<up[x][0]<<" "<<y<<" "<<z<<"\n";
    ebash_tuda(up[x][0],y,z,1);
  }
  if(!par(y,x)){
    // cout<<2<<" "<<y<<" "<<x<<" "<<z<<"\n";
    ebash_tuda(y,x,z,0);
  }

  if(!par(x,y)){
    // cout<<3<<" "<<x<<" "<<y<<" "<<z<<"\n";
    ebash_ottuda(x,y,z,1);
  }
  if(!par(y,x)){
    // cout<<4<<" "<<up[y][0]<<" "<<x<<" "<<z<<"\n";
    ebash_ottuda(up[y][0],x,z,0);
  }
}

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();
  }
 
  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];
  }
  cur=m+n+n;
  dfs(1);
  // cout<<"\n";
  for(int i=1;i<=m;i++){
    add(s[i],t[i],i+n+n);
    g1[s[i]].pb(i+n+n);
    g1[i+n+n].pb(t[i]+n);
    // g1[i+n+n].pb(t[i]+n);
  }
  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

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")
      | 
jail.cpp: In function 'void dfs(int, int)':
jail.cpp:79:13: warning: iteration 19 invokes undefined behavior [-Waggressive-loop-optimizations]
   79 |     in[v][i]=++cur;
      |             ^
jail.cpp:78:16: note: within this loop
   78 |   for(int i=1;i<=L;i++){
      |               ~^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 248148 KB Output is correct
2 Correct 99 ms 248144 KB Output is correct
3 Correct 99 ms 248140 KB Output is correct
4 Correct 115 ms 248404 KB Output is correct
5 Correct 136 ms 248896 KB Output is correct
6 Correct 100 ms 248240 KB Output is correct
7 Correct 101 ms 248344 KB Output is correct
8 Correct 99 ms 248520 KB Output is correct
9 Correct 285 ms 278728 KB Output is correct
10 Correct 2163 ms 786848 KB Output is correct
11 Correct 103 ms 248144 KB Output is correct
12 Correct 152 ms 248244 KB Output is correct
13 Correct 339 ms 385364 KB Output is correct
14 Correct 372 ms 416576 KB Output is correct
15 Runtime error 2378 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 248144 KB Output is correct
2 Correct 100 ms 248148 KB Output is correct
3 Correct 101 ms 248144 KB Output is correct
4 Incorrect 101 ms 248240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 248144 KB Output is correct
2 Correct 100 ms 248148 KB Output is correct
3 Correct 101 ms 248144 KB Output is correct
4 Incorrect 101 ms 248240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 248144 KB Output is correct
2 Correct 100 ms 248148 KB Output is correct
3 Correct 101 ms 248144 KB Output is correct
4 Incorrect 101 ms 248240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 248144 KB Output is correct
2 Correct 100 ms 248148 KB Output is correct
3 Correct 101 ms 248144 KB Output is correct
4 Incorrect 101 ms 248240 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 248144 KB Output is correct
2 Correct 97 ms 248144 KB Output is correct
3 Correct 98 ms 248148 KB Output is correct
4 Correct 103 ms 248024 KB Output is correct
5 Correct 105 ms 248148 KB Output is correct
6 Correct 97 ms 248148 KB Output is correct
7 Incorrect 98 ms 248148 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 248148 KB Output is correct
2 Correct 99 ms 248144 KB Output is correct
3 Correct 99 ms 248140 KB Output is correct
4 Correct 115 ms 248404 KB Output is correct
5 Correct 136 ms 248896 KB Output is correct
6 Correct 100 ms 248240 KB Output is correct
7 Correct 101 ms 248344 KB Output is correct
8 Correct 99 ms 248520 KB Output is correct
9 Correct 285 ms 278728 KB Output is correct
10 Correct 2163 ms 786848 KB Output is correct
11 Correct 103 ms 248144 KB Output is correct
12 Correct 152 ms 248244 KB Output is correct
13 Correct 339 ms 385364 KB Output is correct
14 Correct 372 ms 416576 KB Output is correct
15 Runtime error 2378 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -