Submission #1100660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100660		epicci23	Inside information (BOI21_servers)	C++17	50 / 100	152 ms	49752 KiB

servers

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int N = 1e5 + 2e4 + 5;
const int LOG = 18;
const int INF = 1e9;

struct DSU{
  vector<int> par,siz;
  DSU(int n){
    par.resize(n+5);
    iota(all(par),0LL);
    siz.assign(n+5,1LL);
  }

  int find(int a){
    if(par[a]==a) return a;
    return par[a]=find(par[a]);
  }

  void unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b) return;
    if(siz[a]>siz[b]) swap(a,b);
    siz[b]+=siz[a];
    par[a]=b;
  }
};

int maxi[N][LOG],mini[N][LOG];
int lift[N][LOG],depth[N];
vector<array<int,2>> v[N];

void dfs(int c){
  for(int i=1;i<LOG;i++) lift[c][i]=lift[lift[c][i-1]][i-1];
  
  for(int i=1;i<LOG;i++){
  	int u = maxi[c][i-1];
  	int u2 = maxi[lift[c][i-1]][i-1];
  	if(u==-1 || u2==-1) continue;
  	if(u>maxi[lift[c][i-1]][0]) continue;
    maxi[c][i]=u2;
  }

  for(int i=1;i<LOG;i++){
  	int u = mini[c][i-1];
  	int u2 = mini[lift[c][i-1]][i-1];
  	if(u==-1 || u2==-1) continue;
  	if(u<mini[lift[c][i-1]][0]) continue;
    mini[c][i]=u2;
  }

  for(auto E:v[c]){
   int x=E[0],y=E[1];
   if(x==lift[c][0]) continue;
   depth[x]=depth[c]+1;
   lift[x][0]=c;
   maxi[x][0]=mini[x][0]=y;
   dfs(x);
  }
}

int lca(int a,int b){
  if(depth[a]<depth[b]) swap(a,b);
  for(int i=0;i<LOG;i++) if((depth[a]-depth[b])>>i&1) a=lift[a][i];
  if(a==b) return a;
  for(int i=LOG-1;i>=0;i--){
  	if(lift[a][i]!=lift[b][i]){
  	  a=lift[a][i];
  	  b=lift[b][i];
  	}
  }
  return lift[a][0];
}

int yukari(int a,int u){
  int le = depth[a]-depth[u],lol = 0;
  for(int i=LOG-1;i>=0;i--){
    if(!(le>>i&1)) continue;
    if(maxi[a][i]==-1) return -1;
    if(lol>maxi[a][0]) return -1;
    lol=maxi[a][i];
    a=lift[a][i];
  }
  return lol;
}

int asagi(int a,int u){
  int le = depth[a]-depth[u],lol = INF;
  for(int i=LOG-1;i>=0;i--){
    if(!(le>>i&1)) continue;
    if(mini[a][i]==-1) return -1;
    if(lol<mini[a][0]) return -1;
    lol=mini[a][i];
    a=lift[a][i];
  }
  return lol;
}

bool check(int a,int b){
  if(a==b) return true;
  int c=lca(a,b);
  int hm = yukari(a,c);
  int hm2 = asagi(b,c);
  if(hm==-1 || hm2==-1) return false;
  return hm<=hm2;
}

void _(){

  memset(maxi,-1,sizeof(maxi));
  memset(mini,-1,sizeof(mini));

  int n,q;
  cin >> n >> q;
  DSU dsu(n+5);
  
  vector<bool> ans(q+5,1);
  vector<array<int,2>> bak(q+5);
  int cp=0;
  for(int i=1;i<n+q;i++){
   char op; cin >> op;
   int a,b;
   cin >> a >> b; 
   if(op=='S'){
     v[a].push_back({b,i});
     v[b].push_back({a,i});
     dsu.unite(a,b);
   }
   else{
   	 cp++;
   	 bak[cp]={a,b};
     if(dsu.find(a)!=dsu.find(b)) ans[cp]=0;
   }
  }
 
  dfs(1);
  for(int i=1;i<=q;i++){
    if(!ans[i]) continue;
    int a=bak[i][0],b=bak[i][1];
    ans[i]=check(b,a);
  }

  for(int i=1;i<=q;i++){
    if(ans[i]) cout << "yes\n";
    else cout << "no\n";
  }
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5