oj.uz

Submission #966172

# Submission time Handle Problem Language Result Execution time Memory
966172 2024-04-19T13:26:28 Z shenfe1 Jail (JOI22_jail) C++17
0 / 100
 2462 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){
  use[v]=1;
  for(auto to:g1[v]){
    if(!use[to])dfs1(to);
    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=2*n+1;i<=n+n+m;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 118 ms 247964 KB Output is correct
2 Correct 101 ms 248148 KB Output is correct
3 Correct 96 ms 248128 KB Output is correct
4 Correct 111 ms 248404 KB Output is correct
5 Correct 124 ms 248844 KB Output is correct
6 Correct 100 ms 248148 KB Output is correct
7 Correct 97 ms 248148 KB Output is correct
8 Correct 99 ms 248556 KB Output is correct
9 Correct 259 ms 278880 KB Output is correct
10 Correct 2009 ms 767508 KB Output is correct
11 Correct 116 ms 248144 KB Output is correct
12 Correct 138 ms 248912 KB Output is correct
13 Correct 302 ms 367116 KB Output is correct
14 Correct 361 ms 398156 KB Output is correct
15 Runtime error 2462 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 112 ms 248148 KB Output is correct
2 Correct 98 ms 248144 KB Output is correct
3 Correct 102 ms 248148 KB Output is correct
4 Incorrect 98 ms 248148 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

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

Subtask #4
0 / 28.0

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

Subtask #5
0 / 12.0

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

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 248148 KB Output is correct
2 Correct 104 ms 248140 KB Output is correct
3 Correct 101 ms 248148 KB Output is correct
4 Correct 96 ms 248148 KB Output is correct
5 Correct 101 ms 248324 KB Output is correct
6 Correct 99 ms 248088 KB Output is correct
7 Incorrect 99 ms 248144 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 247964 KB Output is correct
2 Correct 101 ms 248148 KB Output is correct
3 Correct 96 ms 248128 KB Output is correct
4 Correct 111 ms 248404 KB Output is correct
5 Correct 124 ms 248844 KB Output is correct
6 Correct 100 ms 248148 KB Output is correct
7 Correct 97 ms 248148 KB Output is correct
8 Correct 99 ms 248556 KB Output is correct
9 Correct 259 ms 278880 KB Output is correct
10 Correct 2009 ms 767508 KB Output is correct
11 Correct 116 ms 248144 KB Output is correct
12 Correct 138 ms 248912 KB Output is correct
13 Correct 302 ms 367116 KB Output is correct
14 Correct 361 ms 398156 KB Output is correct
15 Runtime error 2462 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -