oj.uz

Submission #966178

# Submission time Handle Problem Language Result Execution time Memory
966178 2024-04-19T13:32:28 Z shenfe1 Jail (JOI22_jail) C++17
100 / 100
 2068 ms 424148 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*3*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*3*L];

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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 147796 KB Output is correct
2 Correct 53 ms 147796 KB Output is correct
3 Correct 47 ms 147800 KB Output is correct
4 Correct 72 ms 148048 KB Output is correct
5 Correct 92 ms 148048 KB Output is correct
6 Correct 53 ms 148284 KB Output is correct
7 Correct 51 ms 148316 KB Output is correct
8 Correct 53 ms 148188 KB Output is correct
9 Correct 216 ms 157568 KB Output is correct
10 Correct 841 ms 333908 KB Output is correct
11 Correct 58 ms 148256 KB Output is correct
12 Correct 118 ms 148672 KB Output is correct
13 Correct 1010 ms 340124 KB Output is correct
14 Correct 1164 ms 347164 KB Output is correct
15 Correct 1445 ms 365792 KB Output is correct
16 Correct 1926 ms 424148 KB Output is correct
17 Correct 1149 ms 343388 KB Output is correct
18 Correct 952 ms 345820 KB Output is correct
19 Correct 1136 ms 343220 KB Output is correct
20 Correct 1113 ms 343400 KB Output is correct
21 Correct 1294 ms 377432 KB Output is correct
22 Correct 873 ms 340644 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 147804 KB Output is correct
2 Correct 49 ms 147792 KB Output is correct
3 Correct 51 ms 148048 KB Output is correct
4 Correct 50 ms 148168 KB Output is correct
5 Correct 50 ms 148056 KB Output is correct
6 Correct 50 ms 148048 KB Output is correct
7 Correct 50 ms 148052 KB Output is correct
8 Correct 52 ms 148052 KB Output is correct
9 Correct 53 ms 148052 KB Output is correct
10 Correct 50 ms 148052 KB Output is correct
11 Correct 50 ms 148052 KB Output is correct
12 Correct 49 ms 148304 KB Output is correct
13 Correct 56 ms 148196 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 147804 KB Output is correct
2 Correct 49 ms 147792 KB Output is correct
3 Correct 51 ms 148048 KB Output is correct
4 Correct 50 ms 148168 KB Output is correct
5 Correct 50 ms 148056 KB Output is correct
6 Correct 50 ms 148048 KB Output is correct
7 Correct 50 ms 148052 KB Output is correct
8 Correct 52 ms 148052 KB Output is correct
9 Correct 53 ms 148052 KB Output is correct
10 Correct 50 ms 148052 KB Output is correct
11 Correct 50 ms 148052 KB Output is correct
12 Correct 49 ms 148304 KB Output is correct
13 Correct 56 ms 148196 KB Output is correct
14 Correct 51 ms 147792 KB Output is correct
15 Correct 50 ms 147668 KB Output is correct
16 Correct 52 ms 148124 KB Output is correct
17 Correct 52 ms 148172 KB Output is correct
18 Correct 51 ms 148296 KB Output is correct
19 Correct 49 ms 147736 KB Output is correct
20 Correct 52 ms 148052 KB Output is correct
21 Correct 53 ms 148048 KB Output is correct
22 Correct 52 ms 148308 KB Output is correct
23 Correct 50 ms 147860 KB Output is correct
24 Correct 50 ms 148052 KB Output is correct
25 Correct 58 ms 148048 KB Output is correct
26 Correct 51 ms 148280 KB Output is correct
27 Correct 53 ms 148052 KB Output is correct
28 Correct 50 ms 147796 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 147804 KB Output is correct
2 Correct 49 ms 147792 KB Output is correct
3 Correct 51 ms 148048 KB Output is correct
4 Correct 50 ms 148168 KB Output is correct
5 Correct 50 ms 148056 KB Output is correct
6 Correct 50 ms 148048 KB Output is correct
7 Correct 50 ms 148052 KB Output is correct
8 Correct 52 ms 148052 KB Output is correct
9 Correct 53 ms 148052 KB Output is correct
10 Correct 50 ms 148052 KB Output is correct
11 Correct 50 ms 148052 KB Output is correct
12 Correct 49 ms 148304 KB Output is correct
13 Correct 56 ms 148196 KB Output is correct
14 Correct 51 ms 147792 KB Output is correct
15 Correct 50 ms 147668 KB Output is correct
16 Correct 52 ms 148124 KB Output is correct
17 Correct 52 ms 148172 KB Output is correct
18 Correct 51 ms 148296 KB Output is correct
19 Correct 49 ms 147736 KB Output is correct
20 Correct 52 ms 148052 KB Output is correct
21 Correct 53 ms 148048 KB Output is correct
22 Correct 52 ms 148308 KB Output is correct
23 Correct 50 ms 147860 KB Output is correct
24 Correct 50 ms 148052 KB Output is correct
25 Correct 58 ms 148048 KB Output is correct
26 Correct 51 ms 148280 KB Output is correct
27 Correct 53 ms 148052 KB Output is correct
28 Correct 50 ms 147796 KB Output is correct
29 Correct 52 ms 148304 KB Output is correct
30 Correct 53 ms 148536 KB Output is correct
31 Correct 54 ms 148428 KB Output is correct
32 Correct 52 ms 148308 KB Output is correct
33 Correct 52 ms 148052 KB Output is correct
34 Correct 59 ms 148052 KB Output is correct
35 Correct 59 ms 148316 KB Output is correct
36 Correct 51 ms 148308 KB Output is correct
37 Correct 51 ms 148124 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 147804 KB Output is correct
2 Correct 49 ms 147792 KB Output is correct
3 Correct 51 ms 148048 KB Output is correct
4 Correct 50 ms 148168 KB Output is correct
5 Correct 50 ms 148056 KB Output is correct
6 Correct 50 ms 148048 KB Output is correct
7 Correct 50 ms 148052 KB Output is correct
8 Correct 52 ms 148052 KB Output is correct
9 Correct 53 ms 148052 KB Output is correct
10 Correct 50 ms 148052 KB Output is correct
11 Correct 50 ms 148052 KB Output is correct
12 Correct 49 ms 148304 KB Output is correct
13 Correct 56 ms 148196 KB Output is correct
14 Correct 51 ms 147792 KB Output is correct
15 Correct 50 ms 147668 KB Output is correct
16 Correct 52 ms 148124 KB Output is correct
17 Correct 52 ms 148172 KB Output is correct
18 Correct 51 ms 148296 KB Output is correct
19 Correct 49 ms 147736 KB Output is correct
20 Correct 52 ms 148052 KB Output is correct
21 Correct 53 ms 148048 KB Output is correct
22 Correct 52 ms 148308 KB Output is correct
23 Correct 50 ms 147860 KB Output is correct
24 Correct 50 ms 148052 KB Output is correct
25 Correct 58 ms 148048 KB Output is correct
26 Correct 51 ms 148280 KB Output is correct
27 Correct 53 ms 148052 KB Output is correct
28 Correct 50 ms 147796 KB Output is correct
29 Correct 52 ms 148304 KB Output is correct
30 Correct 53 ms 148536 KB Output is correct
31 Correct 54 ms 148428 KB Output is correct
32 Correct 52 ms 148308 KB Output is correct
33 Correct 52 ms 148052 KB Output is correct
34 Correct 59 ms 148052 KB Output is correct
35 Correct 59 ms 148316 KB Output is correct
36 Correct 51 ms 148308 KB Output is correct
37 Correct 51 ms 148124 KB Output is correct
38 Correct 281 ms 157444 KB Output is correct
39 Correct 789 ms 333772 KB Output is correct
40 Correct 187 ms 158972 KB Output is correct
41 Correct 136 ms 158328 KB Output is correct
42 Correct 146 ms 158672 KB Output is correct
43 Correct 173 ms 158292 KB Output is correct
44 Correct 65 ms 149588 KB Output is correct
45 Correct 465 ms 321804 KB Output is correct
46 Correct 489 ms 321468 KB Output is correct
47 Correct 777 ms 325996 KB Output is correct
48 Correct 752 ms 325872 KB Output is correct
49 Correct 462 ms 322156 KB Output is correct
50 Correct 468 ms 321708 KB Output is correct
51 Correct 639 ms 327860 KB Output is correct
52 Correct 713 ms 328896 KB Output is correct
53 Correct 90 ms 161192 KB Output is correct
54 Correct 458 ms 319756 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 147792 KB Output is correct
2 Correct 50 ms 147796 KB Output is correct
3 Correct 50 ms 147812 KB Output is correct
4 Correct 49 ms 147792 KB Output is correct
5 Correct 68 ms 147924 KB Output is correct
6 Correct 49 ms 148060 KB Output is correct
7 Correct 51 ms 148048 KB Output is correct
8 Correct 50 ms 147792 KB Output is correct
9 Correct 51 ms 147892 KB Output is correct
10 Correct 50 ms 147864 KB Output is correct
11 Correct 57 ms 147804 KB Output is correct
12 Correct 52 ms 148308 KB Output is correct
13 Correct 84 ms 148048 KB Output is correct
14 Correct 104 ms 148040 KB Output is correct
15 Correct 92 ms 148152 KB Output is correct
16 Correct 495 ms 329604 KB Output is correct
17 Correct 761 ms 340860 KB Output is correct
18 Correct 1020 ms 363556 KB Output is correct
19 Correct 571 ms 331044 KB Output is correct
20 Correct 554 ms 330876 KB Output is correct
21 Correct 543 ms 330844 KB Output is correct
22 Correct 665 ms 337264 KB Output is correct
23 Correct 599 ms 336000 KB Output is correct
24 Correct 650 ms 335608 KB Output is correct
25 Correct 627 ms 335664 KB Output is correct
26 Correct 704 ms 335640 KB Output is correct
27 Correct 652 ms 346868 KB Output is correct
28 Correct 742 ms 349900 KB Output is correct
29 Correct 743 ms 343716 KB Output is correct
30 Correct 653 ms 337576 KB Output is correct
31 Correct 621 ms 338796 KB Output is correct
32 Correct 577 ms 337492 KB Output is correct
33 Correct 588 ms 338760 KB Output is correct

Subtask #7
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 147796 KB Output is correct
2 Correct 53 ms 147796 KB Output is correct
3 Correct 47 ms 147800 KB Output is correct
4 Correct 72 ms 148048 KB Output is correct
5 Correct 92 ms 148048 KB Output is correct
6 Correct 53 ms 148284 KB Output is correct
7 Correct 51 ms 148316 KB Output is correct
8 Correct 53 ms 148188 KB Output is correct
9 Correct 216 ms 157568 KB Output is correct
10 Correct 841 ms 333908 KB Output is correct
11 Correct 58 ms 148256 KB Output is correct
12 Correct 118 ms 148672 KB Output is correct
13 Correct 1010 ms 340124 KB Output is correct
14 Correct 1164 ms 347164 KB Output is correct
15 Correct 1445 ms 365792 KB Output is correct
16 Correct 1926 ms 424148 KB Output is correct
17 Correct 1149 ms 343388 KB Output is correct
18 Correct 952 ms 345820 KB Output is correct
19 Correct 1136 ms 343220 KB Output is correct
20 Correct 1113 ms 343400 KB Output is correct
21 Correct 1294 ms 377432 KB Output is correct
22 Correct 873 ms 340644 KB Output is correct
23 Correct 54 ms 147804 KB Output is correct
24 Correct 49 ms 147792 KB Output is correct
25 Correct 51 ms 148048 KB Output is correct
26 Correct 50 ms 148168 KB Output is correct
27 Correct 50 ms 148056 KB Output is correct
28 Correct 50 ms 148048 KB Output is correct
29 Correct 50 ms 148052 KB Output is correct
30 Correct 52 ms 148052 KB Output is correct
31 Correct 53 ms 148052 KB Output is correct
32 Correct 50 ms 148052 KB Output is correct
33 Correct 50 ms 148052 KB Output is correct
34 Correct 49 ms 148304 KB Output is correct
35 Correct 56 ms 148196 KB Output is correct
36 Correct 51 ms 147792 KB Output is correct
37 Correct 50 ms 147668 KB Output is correct
38 Correct 52 ms 148124 KB Output is correct
39 Correct 52 ms 148172 KB Output is correct
40 Correct 51 ms 148296 KB Output is correct
41 Correct 49 ms 147736 KB Output is correct
42 Correct 52 ms 148052 KB Output is correct
43 Correct 53 ms 148048 KB Output is correct
44 Correct 52 ms 148308 KB Output is correct
45 Correct 50 ms 147860 KB Output is correct
46 Correct 50 ms 148052 KB Output is correct
47 Correct 58 ms 148048 KB Output is correct
48 Correct 51 ms 148280 KB Output is correct
49 Correct 53 ms 148052 KB Output is correct
50 Correct 50 ms 147796 KB Output is correct
51 Correct 52 ms 148304 KB Output is correct
52 Correct 53 ms 148536 KB Output is correct
53 Correct 54 ms 148428 KB Output is correct
54 Correct 52 ms 148308 KB Output is correct
55 Correct 52 ms 148052 KB Output is correct
56 Correct 59 ms 148052 KB Output is correct
57 Correct 59 ms 148316 KB Output is correct
58 Correct 51 ms 148308 KB Output is correct
59 Correct 51 ms 148124 KB Output is correct
60 Correct 281 ms 157444 KB Output is correct
61 Correct 789 ms 333772 KB Output is correct
62 Correct 187 ms 158972 KB Output is correct
63 Correct 136 ms 158328 KB Output is correct
64 Correct 146 ms 158672 KB Output is correct
65 Correct 173 ms 158292 KB Output is correct
66 Correct 65 ms 149588 KB Output is correct
67 Correct 465 ms 321804 KB Output is correct
68 Correct 489 ms 321468 KB Output is correct
69 Correct 777 ms 325996 KB Output is correct
70 Correct 752 ms 325872 KB Output is correct
71 Correct 462 ms 322156 KB Output is correct
72 Correct 468 ms 321708 KB Output is correct
73 Correct 639 ms 327860 KB Output is correct
74 Correct 713 ms 328896 KB Output is correct
75 Correct 90 ms 161192 KB Output is correct
76 Correct 458 ms 319756 KB Output is correct
77 Correct 50 ms 147792 KB Output is correct
78 Correct 50 ms 147796 KB Output is correct
79 Correct 50 ms 147812 KB Output is correct
80 Correct 49 ms 147792 KB Output is correct
81 Correct 68 ms 147924 KB Output is correct
82 Correct 49 ms 148060 KB Output is correct
83 Correct 51 ms 148048 KB Output is correct
84 Correct 50 ms 147792 KB Output is correct
85 Correct 51 ms 147892 KB Output is correct
86 Correct 50 ms 147864 KB Output is correct
87 Correct 57 ms 147804 KB Output is correct
88 Correct 52 ms 148308 KB Output is correct
89 Correct 84 ms 148048 KB Output is correct
90 Correct 104 ms 148040 KB Output is correct
91 Correct 92 ms 148152 KB Output is correct
92 Correct 495 ms 329604 KB Output is correct
93 Correct 761 ms 340860 KB Output is correct
94 Correct 1020 ms 363556 KB Output is correct
95 Correct 571 ms 331044 KB Output is correct
96 Correct 554 ms 330876 KB Output is correct
97 Correct 543 ms 330844 KB Output is correct
98 Correct 665 ms 337264 KB Output is correct
99 Correct 599 ms 336000 KB Output is correct
100 Correct 650 ms 335608 KB Output is correct
101 Correct 627 ms 335664 KB Output is correct
102 Correct 704 ms 335640 KB Output is correct
103 Correct 652 ms 346868 KB Output is correct
104 Correct 742 ms 349900 KB Output is correct
105 Correct 743 ms 343716 KB Output is correct
106 Correct 653 ms 337576 KB Output is correct
107 Correct 621 ms 338796 KB Output is correct
108 Correct 577 ms 337492 KB Output is correct
109 Correct 588 ms 338760 KB Output is correct
110 Correct 109 ms 149528 KB Output is correct
111 Correct 93 ms 148848 KB Output is correct
112 Correct 1543 ms 368732 KB Output is correct
113 Correct 1059 ms 333008 KB Output is correct
114 Correct 914 ms 357932 KB Output is correct
115 Correct 412 ms 330440 KB Output is correct
116 Correct 611 ms 335452 KB Output is correct
117 Correct 1173 ms 374536 KB Output is correct
118 Correct 482 ms 324688 KB Output is correct
119 Correct 464 ms 324640 KB Output is correct
120 Correct 89 ms 163496 KB Output is correct
121 Correct 756 ms 336392 KB Output is correct
122 Correct 767 ms 336652 KB Output is correct
123 Correct 1083 ms 334732 KB Output is correct
124 Correct 1124 ms 334712 KB Output is correct
125 Correct 1075 ms 335140 KB Output is correct
126 Correct 2068 ms 421372 KB Output is correct
127 Correct 1179 ms 376548 KB Output is correct
128 Correct 1110 ms 368680 KB Output is correct
129 Correct 1014 ms 342780 KB Output is correct
130 Correct 1092 ms 370372 KB Output is correct