Submission #1233677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233677		minhpk	Jail (JOI22_jail)	C++20	0 / 100	25 ms	55192 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][21];
pair<int,int> v[1000005];
int up[1000005];
int cnt[1000005];
int cnt1[1000005];
 int a;

void dfs(int i,int par){
    up[i]=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 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)));
}

stack<int> s;
vector <int> z1[1000005];
int  pos[1000005];
bool vis[1000005];
void dfs1(int i){
    vis[i]=true;

    for (auto p:z1[i]){
        if (vis[p]){
            continue;
        }
        dfs1(p);
    }
    s.push(i);
}
int calc(int x,int y){
    return high[x]+high[y]-2*high[lca(x,y)];
}
int duongkinh(){

    int pos=1;
    int dis=0;
    for (int i=1;i<=a;i++){
         if (dis<calc(1,i)){
             dis=calc(1,i);
             pos=i;
         }
    }

    int pos1=pos;
    int dis1=0;

    for (int i=1;i<=a;i++){
         if (dis1<calc(pos,i)){
             dis1=calc(pos,i);
             pos1=i;
         }
    }
    return calc(pos,pos1);
}

void solve(){
    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 diameter=duongkinh();
    int c;
    cin >> c;
    for (int i=1;i<=c;i++){
         cin >> v[i].first >> v[i].second;
         cnt[v[i].first]=v[i].first;
         cnt1[v[i].second]=v[i].first;
    }

//    cout << "\n";
    bool check=true;
   if (diameter>50){
    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) ){
                  z1[u].push_back(x);

//                  cout << j << " " << i << "\n";
              }
              if (onpath(x,y,v1) ){
                  z1[x].push_back(v1);
//                  cout << i << " " << j << "\n";
              }
         }
    }
   }else{
        for (int i=1;i<=c;i++){
             auto [x,y]=v[i];
             int l=lca(x,y);
             int p1=x;
             while (p1!=l){
                  if (cnt[p1]){
                      z1[cnt[p1]].push_back(x);
                  }
                  if (cnt1[p1]){
                      z1[x].push_back(cnt[p1]);
                  }
                  p1=up[p1];
             }
             p1=y;
             while (p1!=l){
                  if (cnt[p1]){
                      z1[cnt[p1]].push_back(x);
                  }
                  if (cnt1[p1]){
                      z1[x].push_back(cnt[p1]);
                  }
                  p1=up[p1];
             }
        }

    }

    for (int i=1;i<=a;i++){
         if (!vis[i]){
             dfs1(i);
         }
    }
    int cur=0;
    while (s.size()){
         cur++;
         int x=s.top();
         s.pop();
         pos[x]=cur;
    }
    for (int i=1;i<=a;i++){
         for (auto p:z1[i]){
             if (pos[i]>pos[p]){
                 check=false;
                 break;
             }
         }
    }

    if (check){
        cout << "Yes" << "\n";
    }else{
        cout << "No" << "\n";
    }
    for (int i=1;i<=max(a,c);i++){
         z[i].clear();
         z1[i].clear();
         vis[i]=false;
         pos[i]=0;
    }
    for (int i=1;i<=a;i++){
        for (int j=0;j<=20;j++){
             st[i][j]=0;
        }
    }
}

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