Submission #1102572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102572		epicci23	Inside information (BOI21_servers)	C++17	100 / 100	249 ms	63424 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 + 4e4 + 5;
const int LOG = 20;
const int INF = 1e9;

int maxi[N][LOG],mini[N][LOG];
int lift[N][LOG],depth[N],ans[N],vis[N],sub[N],comp=0;
vector<array<int,2>> v[N],tag[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);
  }
}

inline 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];
}

inline 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;
}

inline 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;
}

inline int check(int a,int b){
  if(a==b) return 0;
  int c=lca(a,b);
  int hm = yukari(a,c);
  int hm2 = asagi(b,c);
  if(hm==-1 || hm2==-1 || hm>hm2) return -1;
  int xdd = hm;
  if(b!=c) xdd=max(xdd,maxi[b][0]);
  return xdd;
}

void precalc(int c,int p){
  sub[c]=1;
  comp++;
  for(auto E:v[c]){
    int x = E[0];
    if(x==p || vis[x]) continue;
    precalc(x,c);
    sub[c]+=sub[x];
  }
}

int find_centroid(int c,int p){
  for(auto E:v[c]){
    int x = E[0];
    if(x==p || vis[x]) continue;
    if(sub[x]>comp/2) return find_centroid(x,c);
  }
  return c;
}

int fw[N];

inline void Upd(int c,int u){
  for(;c<N;c+=c&-c) fw[c]+=u;    
}

inline int Query(int c,int res=0){
  for(;c;c-=c&-c) res+=fw[c];
  return res;
}

void Add(int c,int p,int last,int val){
  Upd(last,val);
  for(auto E:v[c]){
    int x=E[0],u=E[1];
    if(vis[x] || x==p || last>u) continue;
    Add(x,c,u,val);
  }
}

void Get(int c,int p,int bruh,int azal){
  for(auto x:tag[c]){
    if(bruh>x[0]) continue;
    ans[x[1]]+=Query(x[0])+1;
  }
  for(auto E:v[c]){
    int x=E[0],u=E[1];
    if(vis[x] || x==p || azal<u) continue;
    Get(x,c,bruh,u);
  }
}

void centroid(int c,int p){
  comp=0;precalc(c,p);
  c=find_centroid(c,p);
  sort(all(v[c]),[&](array<int,2> a,array<int,2> b){
    return a[1]>b[1];
  });
  for(auto E:v[c]){
    int x = E[0], u = E[1];
    if(x==p || vis[x]) continue;
    Get(x,c,u,u);
    Add(x,c,u,1);
  }
  for(auto x:tag[c]) ans[x[1]]+=Query(x[0]);
  for(auto E:v[c]){
    int x = E[0], u = E[1];
    if(x==p || vis[x]) continue;
    Add(x,c,u,-1);
  }
  vis[c]=1;
  for(auto E:v[c]){
    int x = E[0], u = E[1];
    if(x==p || vis[x]) continue;
    centroid(x,c);
  }
}

void _(){
  memset(maxi,-1,sizeof(maxi));
  memset(mini,-1,sizeof(mini));

  int n,q;
  cin >> n >> q;
  
  vector<array<int,4>> cevapla;
  int cp=0,ed=0;

  for(int i=1;i<n+q;i++){
    char op;
    cin >> op;
    if(op=='S'){
     int a,b;
     cin >> a >> b;
     ++ed;
     v[a].push_back({b,ed});
     v[b].push_back({a,ed});
    }
    else if(op=='Q'){
      int a,b;
      cin >> a >> b;
      ++cp;
      cevapla.push_back({b,a,ed,cp});
    }
    else{
      int a;
      cin >> a;
      ++cp;
      tag[a].push_back({ed,cp});
    }
  }
  dfs(1);
  for(auto x:cevapla){
    int res = check(x[0],x[1]);
    if(res==-1 || res>x[2]) ans[x[3]]=-2;
    else ans[x[3]]=-1; 
  }
  centroid(1,0);
  for(int i=1;i<=cp;i++){
    if(ans[i]==-2) cout << "no\n";
    else if(ans[i]==-1) cout << "yes\n";
    else cout << ans[i] + 1 << '\n';
  }
}

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

Compilation message (stderr)

servers.cpp: In function 'void centroid(int, int)':
servers.cpp:164:19: warning: unused variable 'u' [-Wunused-variable]
  164 |     int x = E[0], u = E[1];
      |                   ^

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