oj.uz

Submission #966170

# Submission time Handle Problem Language Result Execution time Memory
966170 2024-04-19T13:19:26 Z shenfe1 Jail (JOI22_jail) C++17
0 / 100
 2282 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(!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;
  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 98 ms 248148 KB Output is correct
2 Correct 101 ms 248172 KB Output is correct
3 Correct 96 ms 247952 KB Output is correct
4 Correct 123 ms 248556 KB Output is correct
5 Correct 135 ms 248548 KB Output is correct
6 Correct 108 ms 248284 KB Output is correct
7 Correct 98 ms 248340 KB Output is correct
8 Correct 111 ms 248548 KB Output is correct
9 Correct 282 ms 278612 KB Output is correct
10 Correct 2001 ms 787528 KB Output is correct
11 Correct 106 ms 248144 KB Output is correct
12 Correct 152 ms 249108 KB Output is correct
13 Correct 345 ms 386608 KB Output is correct
14 Correct 359 ms 417872 KB Output is correct
15 Runtime error 2282 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 96 ms 248120 KB Output is correct
2 Correct 125 ms 248152 KB Output is correct
3 Correct 99 ms 248092 KB Output is correct
4 Incorrect 101 ms 248220 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 248120 KB Output is correct
2 Correct 125 ms 248152 KB Output is correct
3 Correct 99 ms 248092 KB Output is correct
4 Incorrect 101 ms 248220 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 248120 KB Output is correct
2 Correct 125 ms 248152 KB Output is correct
3 Correct 99 ms 248092 KB Output is correct
4 Incorrect 101 ms 248220 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 248120 KB Output is correct
2 Correct 125 ms 248152 KB Output is correct
3 Correct 99 ms 248092 KB Output is correct
4 Incorrect 101 ms 248220 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 248048 KB Output is correct
2 Correct 97 ms 248144 KB Output is correct
3 Correct 101 ms 248152 KB Output is correct
4 Correct 99 ms 248124 KB Output is correct
5 Correct 121 ms 248144 KB Output is correct
6 Correct 98 ms 248144 KB Output is correct
7 Incorrect 99 ms 248152 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 248148 KB Output is correct
2 Correct 101 ms 248172 KB Output is correct
3 Correct 96 ms 247952 KB Output is correct
4 Correct 123 ms 248556 KB Output is correct
5 Correct 135 ms 248548 KB Output is correct
6 Correct 108 ms 248284 KB Output is correct
7 Correct 98 ms 248340 KB Output is correct
8 Correct 111 ms 248548 KB Output is correct
9 Correct 282 ms 278612 KB Output is correct
10 Correct 2001 ms 787528 KB Output is correct
11 Correct 106 ms 248144 KB Output is correct
12 Correct 152 ms 249108 KB Output is correct
13 Correct 345 ms 386608 KB Output is correct
14 Correct 359 ms 417872 KB Output is correct
15 Runtime error 2282 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -