oj.uz

Submission #966051

# Submission time Handle Problem Language Result Execution time Memory
966051 2024-04-19T10:02:02 Z shenfe1 Jail (JOI22_jail) C++17
49 / 100
 3095 ms 970172 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 203 ms 377484 KB Output is correct
2 Correct 165 ms 377172 KB Output is correct
3 Correct 162 ms 377172 KB Output is correct
4 Correct 189 ms 377772 KB Output is correct
5 Correct 222 ms 378228 KB Output is correct
6 Correct 158 ms 377936 KB Output is correct
7 Correct 160 ms 377940 KB Output is correct
8 Correct 160 ms 377940 KB Output is correct
9 Correct 684 ms 395700 KB Output is correct
10 Runtime error 3095 ms 967212 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 170 ms 377428 KB Output is correct
2 Correct 184 ms 377184 KB Output is correct
3 Correct 169 ms 377940 KB Output is correct
4 Correct 172 ms 377940 KB Output is correct
5 Correct 173 ms 377936 KB Output is correct
6 Correct 184 ms 377936 KB Output is correct
7 Correct 172 ms 377920 KB Output is correct
8 Correct 170 ms 377940 KB Output is correct
9 Correct 167 ms 377848 KB Output is correct
10 Correct 174 ms 377896 KB Output is correct
11 Correct 169 ms 377940 KB Output is correct
12 Correct 167 ms 377756 KB Output is correct
13 Correct 170 ms 377680 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 377428 KB Output is correct
2 Correct 184 ms 377184 KB Output is correct
3 Correct 169 ms 377940 KB Output is correct
4 Correct 172 ms 377940 KB Output is correct
5 Correct 173 ms 377936 KB Output is correct
6 Correct 184 ms 377936 KB Output is correct
7 Correct 172 ms 377920 KB Output is correct
8 Correct 170 ms 377940 KB Output is correct
9 Correct 167 ms 377848 KB Output is correct
10 Correct 174 ms 377896 KB Output is correct
11 Correct 169 ms 377940 KB Output is correct
12 Correct 167 ms 377756 KB Output is correct
13 Correct 170 ms 377680 KB Output is correct
14 Correct 163 ms 377172 KB Output is correct
15 Correct 167 ms 377236 KB Output is correct
16 Correct 169 ms 377940 KB Output is correct
17 Correct 171 ms 378196 KB Output is correct
18 Correct 168 ms 377944 KB Output is correct
19 Correct 174 ms 377212 KB Output is correct
20 Correct 171 ms 378004 KB Output is correct
21 Correct 170 ms 377940 KB Output is correct
22 Correct 170 ms 377936 KB Output is correct
23 Correct 165 ms 377168 KB Output is correct
24 Correct 167 ms 377436 KB Output is correct
25 Correct 172 ms 377932 KB Output is correct
26 Correct 167 ms 377684 KB Output is correct
27 Correct 181 ms 377788 KB Output is correct
28 Correct 169 ms 377172 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 377428 KB Output is correct
2 Correct 184 ms 377184 KB Output is correct
3 Correct 169 ms 377940 KB Output is correct
4 Correct 172 ms 377940 KB Output is correct
5 Correct 173 ms 377936 KB Output is correct
6 Correct 184 ms 377936 KB Output is correct
7 Correct 172 ms 377920 KB Output is correct
8 Correct 170 ms 377940 KB Output is correct
9 Correct 167 ms 377848 KB Output is correct
10 Correct 174 ms 377896 KB Output is correct
11 Correct 169 ms 377940 KB Output is correct
12 Correct 167 ms 377756 KB Output is correct
13 Correct 170 ms 377680 KB Output is correct
14 Correct 163 ms 377172 KB Output is correct
15 Correct 167 ms 377236 KB Output is correct
16 Correct 169 ms 377940 KB Output is correct
17 Correct 171 ms 378196 KB Output is correct
18 Correct 168 ms 377944 KB Output is correct
19 Correct 174 ms 377212 KB Output is correct
20 Correct 171 ms 378004 KB Output is correct
21 Correct 170 ms 377940 KB Output is correct
22 Correct 170 ms 377936 KB Output is correct
23 Correct 165 ms 377168 KB Output is correct
24 Correct 167 ms 377436 KB Output is correct
25 Correct 172 ms 377932 KB Output is correct
26 Correct 167 ms 377684 KB Output is correct
27 Correct 181 ms 377788 KB Output is correct
28 Correct 169 ms 377172 KB Output is correct
29 Correct 172 ms 378144 KB Output is correct
30 Correct 179 ms 378452 KB Output is correct
31 Correct 171 ms 378352 KB Output is correct
32 Correct 169 ms 377940 KB Output is correct
33 Correct 171 ms 378196 KB Output is correct
34 Correct 170 ms 377856 KB Output is correct
35 Correct 172 ms 377936 KB Output is correct
36 Correct 178 ms 377940 KB Output is correct
37 Correct 168 ms 377792 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 377428 KB Output is correct
2 Correct 184 ms 377184 KB Output is correct
3 Correct 169 ms 377940 KB Output is correct
4 Correct 172 ms 377940 KB Output is correct
5 Correct 173 ms 377936 KB Output is correct
6 Correct 184 ms 377936 KB Output is correct
7 Correct 172 ms 377920 KB Output is correct
8 Correct 170 ms 377940 KB Output is correct
9 Correct 167 ms 377848 KB Output is correct
10 Correct 174 ms 377896 KB Output is correct
11 Correct 169 ms 377940 KB Output is correct
12 Correct 167 ms 377756 KB Output is correct
13 Correct 170 ms 377680 KB Output is correct
14 Correct 163 ms 377172 KB Output is correct
15 Correct 167 ms 377236 KB Output is correct
16 Correct 169 ms 377940 KB Output is correct
17 Correct 171 ms 378196 KB Output is correct
18 Correct 168 ms 377944 KB Output is correct
19 Correct 174 ms 377212 KB Output is correct
20 Correct 171 ms 378004 KB Output is correct
21 Correct 170 ms 377940 KB Output is correct
22 Correct 170 ms 377936 KB Output is correct
23 Correct 165 ms 377168 KB Output is correct
24 Correct 167 ms 377436 KB Output is correct
25 Correct 172 ms 377932 KB Output is correct
26 Correct 167 ms 377684 KB Output is correct
27 Correct 181 ms 377788 KB Output is correct
28 Correct 169 ms 377172 KB Output is correct
29 Correct 172 ms 378144 KB Output is correct
30 Correct 179 ms 378452 KB Output is correct
31 Correct 171 ms 378352 KB Output is correct
32 Correct 169 ms 377940 KB Output is correct
33 Correct 171 ms 378196 KB Output is correct
34 Correct 170 ms 377856 KB Output is correct
35 Correct 172 ms 377936 KB Output is correct
36 Correct 178 ms 377940 KB Output is correct
37 Correct 168 ms 377792 KB Output is correct
38 Correct 701 ms 395748 KB Output is correct
39 Runtime error 2843 ms 968720 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 167 ms 377172 KB Output is correct
2 Correct 167 ms 377172 KB Output is correct
3 Correct 168 ms 377172 KB Output is correct
4 Correct 167 ms 377152 KB Output is correct
5 Correct 179 ms 377512 KB Output is correct
6 Correct 166 ms 377728 KB Output is correct
7 Correct 169 ms 377916 KB Output is correct
8 Correct 168 ms 377272 KB Output is correct
9 Correct 176 ms 377424 KB Output is correct
10 Correct 169 ms 377428 KB Output is correct
11 Correct 166 ms 377256 KB Output is correct
12 Correct 177 ms 377936 KB Output is correct
13 Correct 225 ms 378452 KB Output is correct
14 Correct 241 ms 378456 KB Output is correct
15 Correct 234 ms 378528 KB Output is correct
16 Runtime error 908 ms 970172 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 203 ms 377484 KB Output is correct
2 Correct 165 ms 377172 KB Output is correct
3 Correct 162 ms 377172 KB Output is correct
4 Correct 189 ms 377772 KB Output is correct
5 Correct 222 ms 378228 KB Output is correct
6 Correct 158 ms 377936 KB Output is correct
7 Correct 160 ms 377940 KB Output is correct
8 Correct 160 ms 377940 KB Output is correct
9 Correct 684 ms 395700 KB Output is correct
10 Runtime error 3095 ms 967212 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -