Submission #1233609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233609		minhpk	Jail (JOI22_jail)	C++20	0 / 100	22 ms	31812 KiB

jail

#include <bits/stdc++.h>
#define int long long
using namespace std;
vector <int> z[1000005];
int sta[1000005];
int fin[1000005];
int tour;
int euler[2000005];
int high[1000005];
int logarit[1000005];
int st[400001][20];
pair<int,int> v[1000005];

void dfs(int i,int par){
    tour++;
    sta[i]=tour;
    euler[tour]=i;

    for (auto p:z[i]){
         if (p==par){
             continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         tour++;
         euler[tour]=i;
    }
    tour++;
    fin[i]=tour;
    euler[tour]=i;
}

void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}
int cnt[1000005];
int lca(int x,int y){
    int l = min(sta[x], sta[y]);
    int r = max(sta[x], sta[y]);
    int j = logarit[r - l + 1];
    int idx1 = st[l][j];
    int idx2 = st[r - (1 << j) + 1][j];
    return (high[idx1] < high[idx2] ? idx1 : idx2);
}
bool isanc(int x,int y){
    return sta[x]>=sta[y] && fin[x]<=fin[y];
}

bool onpath(int x,int y,int u){
     int l=lca(x,y);
     return ((isanc(x,u) && isanc(u,l)) || (isanc(y,u) && isanc(u,l)));
}
void solve(){
    int a;
    cin >> a;
    for (int i=1;i<a;i++){
        int x,y;
        cin >> x >> y;
        z[x].push_back(y);
        z[y].push_back(x);
    }
    tour=0;
    dfs(1,0);
    buildst();

    int c;
    cin >> c;
    for (int i=1;i<=c;i++){
         cin >> v[i].first >> v[i].second;
         cnt[v[i].second]++;
    }


    bool check=true;
    for (int i=1;i<=c;i++){
         for (int j=1;j<=c;j++){
            if (i==j){
                continue;
            }
              auto [x,y]=v[i];
              auto [u,v1]=v[j];
              if (onpath(x,y,u) && onpath(x,y,v1)){
                  check=false;
                  break;
              }
              if (onpath(x,y,v1) && onpath(u,v1,y)){
                  check=false;
                  break;
              }
         }
    }
    if (check){
        cout << "Yes" << "\n";
    }else{
        cout << "No" << "\n";
    }
    for (int i=1;i<=a;i++){
         z[i].clear();
         cnt[i]=false;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    logarit[2] = 1;
    for(int i = 3; i <= 1000000; i++){
         logarit[i] = logarit[i/2] + 1;
    }
    while (t--){
         solve();
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23