oj.uz

Submission #966053

# Submission time Handle Problem Language Result Execution time Memory
966053 2024-04-19T10:02:51 Z shenfe1 Jail (JOI22_jail) C++17
49 / 100
 2304 ms 1009772 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());

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;
  in[v][0]=++cur;
  out[v][0]=++cur;

  // cout<<"!!!! "<<v<<"\n";

  // for(int x:pos[v]){
  //   if(x>0){
  //     add(in[v][0],x);
  //   }
  //   else{
  //     add(-x,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]);
}

void addin(int x,int y,int z){
  // for(int i=L;i>=0;i--){
  //   if(d[up[x][i]]>d[y]){
  //     // cout<<x<<" "<<i<<" "<<in[x][i]<<"\n";
  //     add(z,in[x][i]);
  //     x=up[x][i];
  //   }
  // }

  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){
  // for(int i=L;i>=0;i--){
  //   if(d[up[x][i]]>d[y]){
  //     add(out[x][i],z);
  //     x=up[x][i];
  //   }
  // }

  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];

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

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.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 377460 KB Output is correct
2 Correct 152 ms 377280 KB Output is correct
3 Correct 157 ms 377424 KB Output is correct
4 Correct 180 ms 377796 KB Output is correct
5 Correct 219 ms 378252 KB Output is correct
6 Correct 154 ms 377940 KB Output is correct
7 Correct 164 ms 377912 KB Output is correct
8 Correct 161 ms 378196 KB Output is correct
9 Correct 596 ms 391412 KB Output is correct
10 Runtime error 2304 ms 1008400 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 377460 KB Output is correct
2 Correct 177 ms 377532 KB Output is correct
3 Correct 163 ms 377940 KB Output is correct
4 Correct 154 ms 377916 KB Output is correct
5 Correct 169 ms 377928 KB Output is correct
6 Correct 165 ms 377812 KB Output is correct
7 Correct 155 ms 377940 KB Output is correct
8 Correct 155 ms 377684 KB Output is correct
9 Correct 150 ms 377932 KB Output is correct
10 Correct 154 ms 377868 KB Output is correct
11 Correct 153 ms 377908 KB Output is correct
12 Correct 153 ms 377684 KB Output is correct
13 Correct 152 ms 377900 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 377460 KB Output is correct
2 Correct 177 ms 377532 KB Output is correct
3 Correct 163 ms 377940 KB Output is correct
4 Correct 154 ms 377916 KB Output is correct
5 Correct 169 ms 377928 KB Output is correct
6 Correct 165 ms 377812 KB Output is correct
7 Correct 155 ms 377940 KB Output is correct
8 Correct 155 ms 377684 KB Output is correct
9 Correct 150 ms 377932 KB Output is correct
10 Correct 154 ms 377868 KB Output is correct
11 Correct 153 ms 377908 KB Output is correct
12 Correct 153 ms 377684 KB Output is correct
13 Correct 152 ms 377900 KB Output is correct
14 Correct 148 ms 377268 KB Output is correct
15 Correct 147 ms 377264 KB Output is correct
16 Correct 158 ms 377724 KB Output is correct
17 Correct 154 ms 377916 KB Output is correct
18 Correct 151 ms 377848 KB Output is correct
19 Correct 145 ms 377424 KB Output is correct
20 Correct 154 ms 377780 KB Output is correct
21 Correct 151 ms 377896 KB Output is correct
22 Correct 168 ms 377960 KB Output is correct
23 Correct 159 ms 377428 KB Output is correct
24 Correct 149 ms 377464 KB Output is correct
25 Correct 149 ms 378052 KB Output is correct
26 Correct 143 ms 377636 KB Output is correct
27 Correct 144 ms 377704 KB Output is correct
28 Correct 145 ms 377564 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 377460 KB Output is correct
2 Correct 177 ms 377532 KB Output is correct
3 Correct 163 ms 377940 KB Output is correct
4 Correct 154 ms 377916 KB Output is correct
5 Correct 169 ms 377928 KB Output is correct
6 Correct 165 ms 377812 KB Output is correct
7 Correct 155 ms 377940 KB Output is correct
8 Correct 155 ms 377684 KB Output is correct
9 Correct 150 ms 377932 KB Output is correct
10 Correct 154 ms 377868 KB Output is correct
11 Correct 153 ms 377908 KB Output is correct
12 Correct 153 ms 377684 KB Output is correct
13 Correct 152 ms 377900 KB Output is correct
14 Correct 148 ms 377268 KB Output is correct
15 Correct 147 ms 377264 KB Output is correct
16 Correct 158 ms 377724 KB Output is correct
17 Correct 154 ms 377916 KB Output is correct
18 Correct 151 ms 377848 KB Output is correct
19 Correct 145 ms 377424 KB Output is correct
20 Correct 154 ms 377780 KB Output is correct
21 Correct 151 ms 377896 KB Output is correct
22 Correct 168 ms 377960 KB Output is correct
23 Correct 159 ms 377428 KB Output is correct
24 Correct 149 ms 377464 KB Output is correct
25 Correct 149 ms 378052 KB Output is correct
26 Correct 143 ms 377636 KB Output is correct
27 Correct 144 ms 377704 KB Output is correct
28 Correct 145 ms 377564 KB Output is correct
29 Correct 144 ms 378052 KB Output is correct
30 Correct 157 ms 377940 KB Output is correct
31 Correct 145 ms 377940 KB Output is correct
32 Correct 146 ms 378124 KB Output is correct
33 Correct 146 ms 377940 KB Output is correct
34 Correct 154 ms 377780 KB Output is correct
35 Correct 149 ms 378132 KB Output is correct
36 Correct 150 ms 377968 KB Output is correct
37 Correct 158 ms 377852 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 377460 KB Output is correct
2 Correct 177 ms 377532 KB Output is correct
3 Correct 163 ms 377940 KB Output is correct
4 Correct 154 ms 377916 KB Output is correct
5 Correct 169 ms 377928 KB Output is correct
6 Correct 165 ms 377812 KB Output is correct
7 Correct 155 ms 377940 KB Output is correct
8 Correct 155 ms 377684 KB Output is correct
9 Correct 150 ms 377932 KB Output is correct
10 Correct 154 ms 377868 KB Output is correct
11 Correct 153 ms 377908 KB Output is correct
12 Correct 153 ms 377684 KB Output is correct
13 Correct 152 ms 377900 KB Output is correct
14 Correct 148 ms 377268 KB Output is correct
15 Correct 147 ms 377264 KB Output is correct
16 Correct 158 ms 377724 KB Output is correct
17 Correct 154 ms 377916 KB Output is correct
18 Correct 151 ms 377848 KB Output is correct
19 Correct 145 ms 377424 KB Output is correct
20 Correct 154 ms 377780 KB Output is correct
21 Correct 151 ms 377896 KB Output is correct
22 Correct 168 ms 377960 KB Output is correct
23 Correct 159 ms 377428 KB Output is correct
24 Correct 149 ms 377464 KB Output is correct
25 Correct 149 ms 378052 KB Output is correct
26 Correct 143 ms 377636 KB Output is correct
27 Correct 144 ms 377704 KB Output is correct
28 Correct 145 ms 377564 KB Output is correct
29 Correct 144 ms 378052 KB Output is correct
30 Correct 157 ms 377940 KB Output is correct
31 Correct 145 ms 377940 KB Output is correct
32 Correct 146 ms 378124 KB Output is correct
33 Correct 146 ms 377940 KB Output is correct
34 Correct 154 ms 377780 KB Output is correct
35 Correct 149 ms 378132 KB Output is correct
36 Correct 150 ms 377968 KB Output is correct
37 Correct 158 ms 377852 KB Output is correct
38 Correct 665 ms 391300 KB Output is correct
39 Runtime error 1923 ms 1009772 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 377376 KB Output is correct
2 Correct 151 ms 377268 KB Output is correct
3 Correct 147 ms 377364 KB Output is correct
4 Correct 146 ms 377428 KB Output is correct
5 Correct 157 ms 377424 KB Output is correct
6 Correct 152 ms 377816 KB Output is correct
7 Correct 144 ms 377684 KB Output is correct
8 Correct 143 ms 377456 KB Output is correct
9 Correct 149 ms 377428 KB Output is correct
10 Correct 144 ms 377556 KB Output is correct
11 Correct 151 ms 377428 KB Output is correct
12 Correct 146 ms 377884 KB Output is correct
13 Correct 193 ms 378196 KB Output is correct
14 Correct 213 ms 378640 KB Output is correct
15 Correct 199 ms 378456 KB Output is correct
16 Runtime error 911 ms 1003936 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 377460 KB Output is correct
2 Correct 152 ms 377280 KB Output is correct
3 Correct 157 ms 377424 KB Output is correct
4 Correct 180 ms 377796 KB Output is correct
5 Correct 219 ms 378252 KB Output is correct
6 Correct 154 ms 377940 KB Output is correct
7 Correct 164 ms 377912 KB Output is correct
8 Correct 161 ms 378196 KB Output is correct
9 Correct 596 ms 391412 KB Output is correct
10 Runtime error 2304 ms 1008400 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -