oj.uz

Submission #966175

# Submission time Handle Problem Language Result Execution time Memory
966175 2024-04-19T13:29:45 Z shenfe1 Jail (JOI22_jail) C++17
72 / 100
 2571 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=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[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-1;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")
      |

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 60504 KB Output is correct
2 Correct 13 ms 56412 KB Output is correct
3 Correct 13 ms 60508 KB Output is correct
4 Correct 23 ms 61012 KB Output is correct
5 Correct 34 ms 56924 KB Output is correct
6 Correct 15 ms 58716 KB Output is correct
7 Correct 14 ms 58540 KB Output is correct
8 Correct 15 ms 56668 KB Output is correct
9 Correct 163 ms 88268 KB Output is correct
10 Correct 1686 ms 568948 KB Output is correct
11 Correct 18 ms 60764 KB Output is correct
12 Correct 50 ms 61528 KB Output is correct
13 Correct 213 ms 168208 KB Output is correct
14 Correct 250 ms 199416 KB Output is correct
15 Runtime error 2571 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 60668 KB Output is correct
2 Correct 15 ms 60508 KB Output is correct
3 Correct 18 ms 60508 KB Output is correct
4 Correct 21 ms 60664 KB Output is correct
5 Correct 15 ms 60508 KB Output is correct
6 Correct 17 ms 60504 KB Output is correct
7 Correct 15 ms 60508 KB Output is correct
8 Correct 15 ms 60508 KB Output is correct
9 Correct 27 ms 60564 KB Output is correct
10 Correct 15 ms 60508 KB Output is correct
11 Correct 14 ms 60512 KB Output is correct
12 Correct 23 ms 60508 KB Output is correct
13 Correct 14 ms 60508 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 60668 KB Output is correct
2 Correct 15 ms 60508 KB Output is correct
3 Correct 18 ms 60508 KB Output is correct
4 Correct 21 ms 60664 KB Output is correct
5 Correct 15 ms 60508 KB Output is correct
6 Correct 17 ms 60504 KB Output is correct
7 Correct 15 ms 60508 KB Output is correct
8 Correct 15 ms 60508 KB Output is correct
9 Correct 27 ms 60564 KB Output is correct
10 Correct 15 ms 60508 KB Output is correct
11 Correct 14 ms 60512 KB Output is correct
12 Correct 23 ms 60508 KB Output is correct
13 Correct 14 ms 60508 KB Output is correct
14 Correct 18 ms 60504 KB Output is correct
15 Correct 14 ms 60508 KB Output is correct
16 Correct 26 ms 60504 KB Output is correct
17 Correct 19 ms 60508 KB Output is correct
18 Correct 16 ms 60508 KB Output is correct
19 Correct 18 ms 60508 KB Output is correct
20 Correct 26 ms 60508 KB Output is correct
21 Correct 21 ms 60508 KB Output is correct
22 Correct 17 ms 60508 KB Output is correct
23 Correct 15 ms 60508 KB Output is correct
24 Correct 18 ms 60508 KB Output is correct
25 Correct 23 ms 60536 KB Output is correct
26 Correct 16 ms 60508 KB Output is correct
27 Correct 15 ms 60640 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 34 ms 60668 KB Output is correct
2 Correct 15 ms 60508 KB Output is correct
3 Correct 18 ms 60508 KB Output is correct
4 Correct 21 ms 60664 KB Output is correct
5 Correct 15 ms 60508 KB Output is correct
6 Correct 17 ms 60504 KB Output is correct
7 Correct 15 ms 60508 KB Output is correct
8 Correct 15 ms 60508 KB Output is correct
9 Correct 27 ms 60564 KB Output is correct
10 Correct 15 ms 60508 KB Output is correct
11 Correct 14 ms 60512 KB Output is correct
12 Correct 23 ms 60508 KB Output is correct
13 Correct 14 ms 60508 KB Output is correct
14 Correct 18 ms 60504 KB Output is correct
15 Correct 14 ms 60508 KB Output is correct
16 Correct 26 ms 60504 KB Output is correct
17 Correct 19 ms 60508 KB Output is correct
18 Correct 16 ms 60508 KB Output is correct
19 Correct 18 ms 60508 KB Output is correct
20 Correct 26 ms 60508 KB Output is correct
21 Correct 21 ms 60508 KB Output is correct
22 Correct 17 ms 60508 KB Output is correct
23 Correct 15 ms 60508 KB Output is correct
24 Correct 18 ms 60508 KB Output is correct
25 Correct 23 ms 60536 KB Output is correct
26 Correct 16 ms 60508 KB Output is correct
27 Correct 15 ms 60640 KB Output is correct
28 Correct 14 ms 60508 KB Output is correct
29 Correct 34 ms 60896 KB Output is correct
30 Correct 18 ms 60508 KB Output is correct
31 Correct 15 ms 60760 KB Output is correct
32 Correct 15 ms 60800 KB Output is correct
33 Correct 34 ms 60496 KB Output is correct
34 Correct 15 ms 60504 KB Output is correct
35 Correct 32 ms 60760 KB Output is correct
36 Correct 21 ms 60764 KB Output is correct
37 Correct 15 ms 60744 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 60668 KB Output is correct
2 Correct 15 ms 60508 KB Output is correct
3 Correct 18 ms 60508 KB Output is correct
4 Correct 21 ms 60664 KB Output is correct
5 Correct 15 ms 60508 KB Output is correct
6 Correct 17 ms 60504 KB Output is correct
7 Correct 15 ms 60508 KB Output is correct
8 Correct 15 ms 60508 KB Output is correct
9 Correct 27 ms 60564 KB Output is correct
10 Correct 15 ms 60508 KB Output is correct
11 Correct 14 ms 60512 KB Output is correct
12 Correct 23 ms 60508 KB Output is correct
13 Correct 14 ms 60508 KB Output is correct
14 Correct 18 ms 60504 KB Output is correct
15 Correct 14 ms 60508 KB Output is correct
16 Correct 26 ms 60504 KB Output is correct
17 Correct 19 ms 60508 KB Output is correct
18 Correct 16 ms 60508 KB Output is correct
19 Correct 18 ms 60508 KB Output is correct
20 Correct 26 ms 60508 KB Output is correct
21 Correct 21 ms 60508 KB Output is correct
22 Correct 17 ms 60508 KB Output is correct
23 Correct 15 ms 60508 KB Output is correct
24 Correct 18 ms 60508 KB Output is correct
25 Correct 23 ms 60536 KB Output is correct
26 Correct 16 ms 60508 KB Output is correct
27 Correct 15 ms 60640 KB Output is correct
28 Correct 14 ms 60508 KB Output is correct
29 Correct 34 ms 60896 KB Output is correct
30 Correct 18 ms 60508 KB Output is correct
31 Correct 15 ms 60760 KB Output is correct
32 Correct 15 ms 60800 KB Output is correct
33 Correct 34 ms 60496 KB Output is correct
34 Correct 15 ms 60504 KB Output is correct
35 Correct 32 ms 60760 KB Output is correct
36 Correct 21 ms 60764 KB Output is correct
37 Correct 15 ms 60744 KB Output is correct
38 Correct 206 ms 95316 KB Output is correct
39 Correct 1908 ms 569060 KB Output is correct
40 Correct 132 ms 79184 KB Output is correct
41 Correct 67 ms 68692 KB Output is correct
42 Correct 80 ms 78160 KB Output is correct
43 Correct 47 ms 68488 KB Output is correct
44 Correct 35 ms 61024 KB Output is correct
45 Correct 95 ms 86104 KB Output is correct
46 Correct 91 ms 86104 KB Output is correct
47 Correct 333 ms 176312 KB Output is correct
48 Correct 335 ms 178956 KB Output is correct
49 Correct 90 ms 90648 KB Output is correct
50 Correct 110 ms 91120 KB Output is correct
51 Correct 58 ms 86432 KB Output is correct
52 Correct 63 ms 86356 KB Output is correct
53 Correct 31 ms 67672 KB Output is correct
54 Correct 102 ms 85324 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 60508 KB Output is correct
2 Correct 20 ms 60504 KB Output is correct
3 Correct 14 ms 60508 KB Output is correct
4 Correct 16 ms 60636 KB Output is correct
5 Correct 24 ms 60764 KB Output is correct
6 Correct 22 ms 60544 KB Output is correct
7 Correct 16 ms 60504 KB Output is correct
8 Correct 15 ms 60508 KB Output is correct
9 Correct 14 ms 60580 KB Output is correct
10 Correct 14 ms 60508 KB Output is correct
11 Correct 17 ms 60508 KB Output is correct
12 Correct 24 ms 60508 KB Output is correct
13 Correct 41 ms 61016 KB Output is correct
14 Correct 45 ms 61308 KB Output is correct
15 Correct 37 ms 61276 KB Output is correct
16 Correct 104 ms 88368 KB Output is correct
17 Correct 227 ms 102908 KB Output is correct
18 Correct 379 ms 125284 KB Output is correct
19 Correct 123 ms 91588 KB Output is correct
20 Correct 130 ms 91840 KB Output is correct
21 Correct 125 ms 91772 KB Output is correct
22 Correct 171 ms 102472 KB Output is correct
23 Correct 175 ms 102120 KB Output is correct
24 Correct 180 ms 102544 KB Output is correct
25 Correct 159 ms 102720 KB Output is correct
26 Correct 176 ms 102684 KB Output is correct
27 Correct 200 ms 107616 KB Output is correct
28 Correct 194 ms 110408 KB Output is correct
29 Correct 188 ms 104896 KB Output is correct
30 Correct 137 ms 98636 KB Output is correct
31 Correct 129 ms 99788 KB Output is correct
32 Correct 154 ms 96512 KB Output is correct
33 Correct 146 ms 97744 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 60504 KB Output is correct
2 Correct 13 ms 56412 KB Output is correct
3 Correct 13 ms 60508 KB Output is correct
4 Correct 23 ms 61012 KB Output is correct
5 Correct 34 ms 56924 KB Output is correct
6 Correct 15 ms 58716 KB Output is correct
7 Correct 14 ms 58540 KB Output is correct
8 Correct 15 ms 56668 KB Output is correct
9 Correct 163 ms 88268 KB Output is correct
10 Correct 1686 ms 568948 KB Output is correct
11 Correct 18 ms 60764 KB Output is correct
12 Correct 50 ms 61528 KB Output is correct
13 Correct 213 ms 168208 KB Output is correct
14 Correct 250 ms 199416 KB Output is correct
15 Runtime error 2571 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -