oj.uz

Submission #966177

# Submission time Handle Problem Language Result Execution time Memory
966177 2024-04-19T13:31:20 Z shenfe1 Jail (JOI22_jail) C++17
49 / 100
 318 ms 288448 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=12e4+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=17;
 
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-1;i>=0;i--){
    if(!par(up[x][i],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-1;i>=0;i--){
    if(!par(up[x][i],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")
      |

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 60752 KB Output is correct
2 Correct 16 ms 60508 KB Output is correct
3 Correct 13 ms 60508 KB Output is correct
4 Correct 39 ms 61140 KB Output is correct
5 Correct 56 ms 61296 KB Output is correct
6 Correct 15 ms 61004 KB Output is correct
7 Correct 16 ms 61016 KB Output is correct
8 Correct 18 ms 61016 KB Output is correct
9 Correct 174 ms 73928 KB Output is correct
10 Runtime error 318 ms 283928 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 14 ms 60504 KB Output is correct
2 Correct 13 ms 60516 KB Output is correct
3 Correct 15 ms 60764 KB Output is correct
4 Correct 16 ms 60760 KB Output is correct
5 Correct 16 ms 60764 KB Output is correct
6 Correct 16 ms 60760 KB Output is correct
7 Correct 17 ms 60764 KB Output is correct
8 Correct 16 ms 60780 KB Output is correct
9 Correct 16 ms 60964 KB Output is correct
10 Correct 16 ms 60764 KB Output is correct
11 Correct 16 ms 60880 KB Output is correct
12 Correct 14 ms 60764 KB Output is correct
13 Correct 14 ms 60800 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 60504 KB Output is correct
2 Correct 13 ms 60516 KB Output is correct
3 Correct 15 ms 60764 KB Output is correct
4 Correct 16 ms 60760 KB Output is correct
5 Correct 16 ms 60764 KB Output is correct
6 Correct 16 ms 60760 KB Output is correct
7 Correct 17 ms 60764 KB Output is correct
8 Correct 16 ms 60780 KB Output is correct
9 Correct 16 ms 60964 KB Output is correct
10 Correct 16 ms 60764 KB Output is correct
11 Correct 16 ms 60880 KB Output is correct
12 Correct 14 ms 60764 KB Output is correct
13 Correct 14 ms 60800 KB Output is correct
14 Correct 13 ms 60508 KB Output is correct
15 Correct 13 ms 60644 KB Output is correct
16 Correct 15 ms 60764 KB Output is correct
17 Correct 16 ms 61016 KB Output is correct
18 Correct 16 ms 60764 KB Output is correct
19 Correct 13 ms 60504 KB Output is correct
20 Correct 16 ms 60764 KB Output is correct
21 Correct 16 ms 60764 KB Output is correct
22 Correct 16 ms 61020 KB Output is correct
23 Correct 13 ms 60504 KB Output is correct
24 Correct 14 ms 60764 KB Output is correct
25 Correct 16 ms 61016 KB Output is correct
26 Correct 14 ms 60764 KB Output is correct
27 Correct 15 ms 61004 KB Output is correct
28 Correct 14 ms 60508 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 60504 KB Output is correct
2 Correct 13 ms 60516 KB Output is correct
3 Correct 15 ms 60764 KB Output is correct
4 Correct 16 ms 60760 KB Output is correct
5 Correct 16 ms 60764 KB Output is correct
6 Correct 16 ms 60760 KB Output is correct
7 Correct 17 ms 60764 KB Output is correct
8 Correct 16 ms 60780 KB Output is correct
9 Correct 16 ms 60964 KB Output is correct
10 Correct 16 ms 60764 KB Output is correct
11 Correct 16 ms 60880 KB Output is correct
12 Correct 14 ms 60764 KB Output is correct
13 Correct 14 ms 60800 KB Output is correct
14 Correct 13 ms 60508 KB Output is correct
15 Correct 13 ms 60644 KB Output is correct
16 Correct 15 ms 60764 KB Output is correct
17 Correct 16 ms 61016 KB Output is correct
18 Correct 16 ms 60764 KB Output is correct
19 Correct 13 ms 60504 KB Output is correct
20 Correct 16 ms 60764 KB Output is correct
21 Correct 16 ms 60764 KB Output is correct
22 Correct 16 ms 61020 KB Output is correct
23 Correct 13 ms 60504 KB Output is correct
24 Correct 14 ms 60764 KB Output is correct
25 Correct 16 ms 61016 KB Output is correct
26 Correct 14 ms 60764 KB Output is correct
27 Correct 15 ms 61004 KB Output is correct
28 Correct 14 ms 60508 KB Output is correct
29 Correct 17 ms 60760 KB Output is correct
30 Correct 17 ms 61020 KB Output is correct
31 Correct 18 ms 61056 KB Output is correct
32 Correct 17 ms 60764 KB Output is correct
33 Correct 17 ms 60764 KB Output is correct
34 Correct 16 ms 60940 KB Output is correct
35 Correct 16 ms 60764 KB Output is correct
36 Correct 17 ms 61020 KB Output is correct
37 Correct 16 ms 60960 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 60504 KB Output is correct
2 Correct 13 ms 60516 KB Output is correct
3 Correct 15 ms 60764 KB Output is correct
4 Correct 16 ms 60760 KB Output is correct
5 Correct 16 ms 60764 KB Output is correct
6 Correct 16 ms 60760 KB Output is correct
7 Correct 17 ms 60764 KB Output is correct
8 Correct 16 ms 60780 KB Output is correct
9 Correct 16 ms 60964 KB Output is correct
10 Correct 16 ms 60764 KB Output is correct
11 Correct 16 ms 60880 KB Output is correct
12 Correct 14 ms 60764 KB Output is correct
13 Correct 14 ms 60800 KB Output is correct
14 Correct 13 ms 60508 KB Output is correct
15 Correct 13 ms 60644 KB Output is correct
16 Correct 15 ms 60764 KB Output is correct
17 Correct 16 ms 61016 KB Output is correct
18 Correct 16 ms 60764 KB Output is correct
19 Correct 13 ms 60504 KB Output is correct
20 Correct 16 ms 60764 KB Output is correct
21 Correct 16 ms 60764 KB Output is correct
22 Correct 16 ms 61020 KB Output is correct
23 Correct 13 ms 60504 KB Output is correct
24 Correct 14 ms 60764 KB Output is correct
25 Correct 16 ms 61016 KB Output is correct
26 Correct 14 ms 60764 KB Output is correct
27 Correct 15 ms 61004 KB Output is correct
28 Correct 14 ms 60508 KB Output is correct
29 Correct 17 ms 60760 KB Output is correct
30 Correct 17 ms 61020 KB Output is correct
31 Correct 18 ms 61056 KB Output is correct
32 Correct 17 ms 60764 KB Output is correct
33 Correct 17 ms 60764 KB Output is correct
34 Correct 16 ms 60940 KB Output is correct
35 Correct 16 ms 60764 KB Output is correct
36 Correct 17 ms 61020 KB Output is correct
37 Correct 16 ms 60960 KB Output is correct
38 Correct 181 ms 73040 KB Output is correct
39 Runtime error 304 ms 282588 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 14 ms 60520 KB Output is correct
2 Correct 13 ms 60508 KB Output is correct
3 Correct 14 ms 60512 KB Output is correct
4 Correct 14 ms 60760 KB Output is correct
5 Correct 26 ms 60764 KB Output is correct
6 Correct 14 ms 60760 KB Output is correct
7 Correct 15 ms 60980 KB Output is correct
8 Correct 13 ms 60508 KB Output is correct
9 Correct 13 ms 60508 KB Output is correct
10 Correct 13 ms 60764 KB Output is correct
11 Correct 14 ms 60788 KB Output is correct
12 Correct 16 ms 61016 KB Output is correct
13 Correct 47 ms 60764 KB Output is correct
14 Correct 64 ms 60760 KB Output is correct
15 Correct 57 ms 60764 KB Output is correct
16 Runtime error 268 ms 288448 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 21 ms 60752 KB Output is correct
2 Correct 16 ms 60508 KB Output is correct
3 Correct 13 ms 60508 KB Output is correct
4 Correct 39 ms 61140 KB Output is correct
5 Correct 56 ms 61296 KB Output is correct
6 Correct 15 ms 61004 KB Output is correct
7 Correct 16 ms 61016 KB Output is correct
8 Correct 18 ms 61016 KB Output is correct
9 Correct 174 ms 73928 KB Output is correct
10 Runtime error 318 ms 283928 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -