oj.uz

Submission #966061

# Submission time Handle Problem Language Result Execution time Memory
966061 2024-04-19T10:07:21 Z shenfe1 Jail (JOI22_jail) C++17
72 / 100
 5000 ms 854160 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;

  for(int i=1;i<=L;i++){
    up[v][i]=up[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){
  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){
  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*30];

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 188 ms 376664 KB Output is correct
2 Correct 139 ms 376716 KB Output is correct
3 Correct 156 ms 376916 KB Output is correct
4 Correct 147 ms 376740 KB Output is correct
5 Correct 240 ms 376560 KB Output is correct
6 Correct 142 ms 376768 KB Output is correct
7 Correct 141 ms 376660 KB Output is correct
8 Correct 143 ms 376696 KB Output is correct
9 Correct 264 ms 379804 KB Output is correct
10 Correct 821 ms 400332 KB Output is correct
11 Correct 151 ms 376804 KB Output is correct
12 Correct 179 ms 377636 KB Output is correct
13 Correct 280 ms 434360 KB Output is correct
14 Correct 315 ms 448080 KB Output is correct
15 Execution timed out 5042 ms 854160 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 376656 KB Output is correct
2 Correct 141 ms 376696 KB Output is correct
3 Correct 142 ms 376660 KB Output is correct
4 Correct 147 ms 376972 KB Output is correct
5 Correct 138 ms 376536 KB Output is correct
6 Correct 140 ms 376616 KB Output is correct
7 Correct 142 ms 376992 KB Output is correct
8 Correct 141 ms 376660 KB Output is correct
9 Correct 138 ms 376660 KB Output is correct
10 Correct 153 ms 376552 KB Output is correct
11 Correct 139 ms 376656 KB Output is correct
12 Correct 141 ms 376660 KB Output is correct
13 Correct 140 ms 376660 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 376656 KB Output is correct
2 Correct 141 ms 376696 KB Output is correct
3 Correct 142 ms 376660 KB Output is correct
4 Correct 147 ms 376972 KB Output is correct
5 Correct 138 ms 376536 KB Output is correct
6 Correct 140 ms 376616 KB Output is correct
7 Correct 142 ms 376992 KB Output is correct
8 Correct 141 ms 376660 KB Output is correct
9 Correct 138 ms 376660 KB Output is correct
10 Correct 153 ms 376552 KB Output is correct
11 Correct 139 ms 376656 KB Output is correct
12 Correct 141 ms 376660 KB Output is correct
13 Correct 140 ms 376660 KB Output is correct
14 Correct 142 ms 376660 KB Output is correct
15 Correct 140 ms 376612 KB Output is correct
16 Correct 139 ms 376768 KB Output is correct
17 Correct 144 ms 376644 KB Output is correct
18 Correct 145 ms 377156 KB Output is correct
19 Correct 140 ms 376524 KB Output is correct
20 Correct 141 ms 376648 KB Output is correct
21 Correct 160 ms 376784 KB Output is correct
22 Correct 140 ms 376916 KB Output is correct
23 Correct 141 ms 376528 KB Output is correct
24 Correct 145 ms 376492 KB Output is correct
25 Correct 144 ms 377168 KB Output is correct
26 Correct 154 ms 376604 KB Output is correct
27 Correct 142 ms 376608 KB Output is correct
28 Correct 139 ms 376656 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 376656 KB Output is correct
2 Correct 141 ms 376696 KB Output is correct
3 Correct 142 ms 376660 KB Output is correct
4 Correct 147 ms 376972 KB Output is correct
5 Correct 138 ms 376536 KB Output is correct
6 Correct 140 ms 376616 KB Output is correct
7 Correct 142 ms 376992 KB Output is correct
8 Correct 141 ms 376660 KB Output is correct
9 Correct 138 ms 376660 KB Output is correct
10 Correct 153 ms 376552 KB Output is correct
11 Correct 139 ms 376656 KB Output is correct
12 Correct 141 ms 376660 KB Output is correct
13 Correct 140 ms 376660 KB Output is correct
14 Correct 142 ms 376660 KB Output is correct
15 Correct 140 ms 376612 KB Output is correct
16 Correct 139 ms 376768 KB Output is correct
17 Correct 144 ms 376644 KB Output is correct
18 Correct 145 ms 377156 KB Output is correct
19 Correct 140 ms 376524 KB Output is correct
20 Correct 141 ms 376648 KB Output is correct
21 Correct 160 ms 376784 KB Output is correct
22 Correct 140 ms 376916 KB Output is correct
23 Correct 141 ms 376528 KB Output is correct
24 Correct 145 ms 376492 KB Output is correct
25 Correct 144 ms 377168 KB Output is correct
26 Correct 154 ms 376604 KB Output is correct
27 Correct 142 ms 376608 KB Output is correct
28 Correct 139 ms 376656 KB Output is correct
29 Correct 144 ms 377076 KB Output is correct
30 Correct 143 ms 376664 KB Output is correct
31 Correct 143 ms 376660 KB Output is correct
32 Correct 145 ms 376812 KB Output is correct
33 Correct 141 ms 376660 KB Output is correct
34 Correct 140 ms 376664 KB Output is correct
35 Correct 152 ms 376840 KB Output is correct
36 Correct 139 ms 376612 KB Output is correct
37 Correct 140 ms 376768 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 376656 KB Output is correct
2 Correct 141 ms 376696 KB Output is correct
3 Correct 142 ms 376660 KB Output is correct
4 Correct 147 ms 376972 KB Output is correct
5 Correct 138 ms 376536 KB Output is correct
6 Correct 140 ms 376616 KB Output is correct
7 Correct 142 ms 376992 KB Output is correct
8 Correct 141 ms 376660 KB Output is correct
9 Correct 138 ms 376660 KB Output is correct
10 Correct 153 ms 376552 KB Output is correct
11 Correct 139 ms 376656 KB Output is correct
12 Correct 141 ms 376660 KB Output is correct
13 Correct 140 ms 376660 KB Output is correct
14 Correct 142 ms 376660 KB Output is correct
15 Correct 140 ms 376612 KB Output is correct
16 Correct 139 ms 376768 KB Output is correct
17 Correct 144 ms 376644 KB Output is correct
18 Correct 145 ms 377156 KB Output is correct
19 Correct 140 ms 376524 KB Output is correct
20 Correct 141 ms 376648 KB Output is correct
21 Correct 160 ms 376784 KB Output is correct
22 Correct 140 ms 376916 KB Output is correct
23 Correct 141 ms 376528 KB Output is correct
24 Correct 145 ms 376492 KB Output is correct
25 Correct 144 ms 377168 KB Output is correct
26 Correct 154 ms 376604 KB Output is correct
27 Correct 142 ms 376608 KB Output is correct
28 Correct 139 ms 376656 KB Output is correct
29 Correct 144 ms 377076 KB Output is correct
30 Correct 143 ms 376664 KB Output is correct
31 Correct 143 ms 376660 KB Output is correct
32 Correct 145 ms 376812 KB Output is correct
33 Correct 141 ms 376660 KB Output is correct
34 Correct 140 ms 376664 KB Output is correct
35 Correct 152 ms 376840 KB Output is correct
36 Correct 139 ms 376612 KB Output is correct
37 Correct 140 ms 376768 KB Output is correct
38 Correct 258 ms 379724 KB Output is correct
39 Correct 805 ms 400136 KB Output is correct
40 Correct 227 ms 379984 KB Output is correct
41 Correct 173 ms 378704 KB Output is correct
42 Correct 202 ms 380136 KB Output is correct
43 Correct 166 ms 378548 KB Output is correct
44 Correct 149 ms 377172 KB Output is correct
45 Correct 224 ms 392756 KB Output is correct
46 Correct 202 ms 392588 KB Output is correct
47 Correct 297 ms 396372 KB Output is correct
48 Correct 308 ms 396396 KB Output is correct
49 Correct 211 ms 392844 KB Output is correct
50 Correct 199 ms 392884 KB Output is correct
51 Correct 180 ms 393936 KB Output is correct
52 Correct 178 ms 393808 KB Output is correct
53 Correct 151 ms 377920 KB Output is correct
54 Correct 223 ms 392992 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 376660 KB Output is correct
2 Correct 141 ms 376712 KB Output is correct
3 Correct 146 ms 376600 KB Output is correct
4 Correct 140 ms 376720 KB Output is correct
5 Correct 145 ms 376728 KB Output is correct
6 Correct 139 ms 376656 KB Output is correct
7 Correct 146 ms 376660 KB Output is correct
8 Correct 140 ms 376656 KB Output is correct
9 Correct 140 ms 376500 KB Output is correct
10 Correct 154 ms 376644 KB Output is correct
11 Correct 145 ms 376584 KB Output is correct
12 Correct 140 ms 376660 KB Output is correct
13 Correct 169 ms 376944 KB Output is correct
14 Correct 169 ms 376748 KB Output is correct
15 Correct 166 ms 376580 KB Output is correct
16 Correct 206 ms 392276 KB Output is correct
17 Correct 300 ms 403376 KB Output is correct
18 Correct 586 ms 428340 KB Output is correct
19 Correct 212 ms 394340 KB Output is correct
20 Correct 212 ms 394732 KB Output is correct
21 Correct 341 ms 394580 KB Output is correct
22 Correct 290 ms 404684 KB Output is correct
23 Correct 257 ms 404552 KB Output is correct
24 Correct 260 ms 404428 KB Output is correct
25 Correct 268 ms 404556 KB Output is correct
26 Correct 258 ms 404664 KB Output is correct
27 Correct 290 ms 407748 KB Output is correct
28 Correct 332 ms 409404 KB Output is correct
29 Correct 311 ms 405952 KB Output is correct
30 Correct 245 ms 402128 KB Output is correct
31 Correct 269 ms 402640 KB Output is correct
32 Correct 242 ms 401968 KB Output is correct
33 Correct 259 ms 402780 KB Output is correct

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 376664 KB Output is correct
2 Correct 139 ms 376716 KB Output is correct
3 Correct 156 ms 376916 KB Output is correct
4 Correct 147 ms 376740 KB Output is correct
5 Correct 240 ms 376560 KB Output is correct
6 Correct 142 ms 376768 KB Output is correct
7 Correct 141 ms 376660 KB Output is correct
8 Correct 143 ms 376696 KB Output is correct
9 Correct 264 ms 379804 KB Output is correct
10 Correct 821 ms 400332 KB Output is correct
11 Correct 151 ms 376804 KB Output is correct
12 Correct 179 ms 377636 KB Output is correct
13 Correct 280 ms 434360 KB Output is correct
14 Correct 315 ms 448080 KB Output is correct
15 Execution timed out 5042 ms 854160 KB Time limit exceeded
16 Halted 0 ms 0 KB -