oj.uz

Submission #966161

# Submission time Handle Problem Language Result Execution time Memory
966161 2024-04-19T12:56:12 Z shenfe1 Jail (JOI22_jail) C++17
0 / 100
 3704 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,0);
  }
  if(!par(y,x)){
    // cout<<4<<" "<<up[y][0]<<" "<<x<<" "<<z<<"\n";
    ebash_ottuda(up[y][0],x,z,1);
  }
}

void solve(){
  cin>>n;
  
  bad=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);
  }
  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 102 ms 248160 KB Output is correct
2 Correct 97 ms 248144 KB Output is correct
3 Correct 95 ms 248148 KB Output is correct
4 Correct 131 ms 248356 KB Output is correct
5 Correct 191 ms 248452 KB Output is correct
6 Correct 103 ms 248404 KB Output is correct
7 Correct 101 ms 248420 KB Output is correct
8 Correct 101 ms 248636 KB Output is correct
9 Correct 588 ms 286824 KB Output is correct
10 Correct 3704 ms 953556 KB Output is correct
11 Correct 134 ms 248148 KB Output is correct
12 Correct 207 ms 249480 KB Output is correct
13 Correct 1452 ms 551680 KB Output is correct
14 Correct 1662 ms 581988 KB Output is correct
15 Runtime error 2132 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 110 ms 248092 KB Output is correct
2 Correct 108 ms 248088 KB Output is correct
3 Correct 111 ms 248560 KB Output is correct
4 Incorrect 111 ms 248572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 248092 KB Output is correct
2 Correct 108 ms 248088 KB Output is correct
3 Correct 111 ms 248560 KB Output is correct
4 Incorrect 111 ms 248572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 248092 KB Output is correct
2 Correct 108 ms 248088 KB Output is correct
3 Correct 111 ms 248560 KB Output is correct
4 Incorrect 111 ms 248572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 248092 KB Output is correct
2 Correct 108 ms 248088 KB Output is correct
3 Correct 111 ms 248560 KB Output is correct
4 Incorrect 111 ms 248572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 248404 KB Output is correct
2 Correct 117 ms 248024 KB Output is correct
3 Correct 109 ms 248140 KB Output is correct
4 Correct 112 ms 247960 KB Output is correct
5 Correct 128 ms 248600 KB Output is correct
6 Correct 116 ms 248456 KB Output is correct
7 Incorrect 113 ms 248496 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 248160 KB Output is correct
2 Correct 97 ms 248144 KB Output is correct
3 Correct 95 ms 248148 KB Output is correct
4 Correct 131 ms 248356 KB Output is correct
5 Correct 191 ms 248452 KB Output is correct
6 Correct 103 ms 248404 KB Output is correct
7 Correct 101 ms 248420 KB Output is correct
8 Correct 101 ms 248636 KB Output is correct
9 Correct 588 ms 286824 KB Output is correct
10 Correct 3704 ms 953556 KB Output is correct
11 Correct 134 ms 248148 KB Output is correct
12 Correct 207 ms 249480 KB Output is correct
13 Correct 1452 ms 551680 KB Output is correct
14 Correct 1662 ms 581988 KB Output is correct
15 Runtime error 2132 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -