Submission #899005

#	Time	Username	Problem	Language	Result	Execution time	Memory
899005		Iliya_	Inside information (BOI21_servers)	C++17	0 / 100	37 ms	65660 KiB

servers

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl        '\n'
#define F           first
#define S           second
#define pii         pair<int,int>
#define all(x)      x.begin(),x.end()
#define pb          push_back
#define fast_io     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define file_io     freopen("input.in" , "r" , stdin) ; freopen("output.out" , "w" , stdout);
using namespace std;
typedef long long ll; 
typedef long double dll;

const int N = 3e5+7, lg = 23; 
char t[N]; 
int a[N], b[N], par[lg][N], dp[lg][N], tadd[N], h[N], mark[N], p[N], siz[N]; 
vector<pii> g[N]; 

void dfs(int v){
     mark[v] = 1;
     for(int i=1; i<lg; i++) par[i][v] = par[i-1][par[i-1][v]]; 
     for(int i=1; i<lg; i++) dp[i][v] = dp[i-1][v] + dp[i-1][par[i-1][v]];      
     for(pii cur : g[v]){
          int u = cur.F, tim = cur.S; 
          if (mark[u]) continue; 
          tadd[u] = tim;
          par[0][u] = v; 
          dp[0][u] = (tadd[u] < tadd[v]); 
          h[u] = h[v] + 1;
          dfs(u); 
     }
}

int lca(int v, int u){
     if (h[v] < h[u]) swap(v,u);
     int dif = h[v] - h[u]; 
     for(int i=lg-1; i>=0; i--) if ((dif>>i)&1) v = par[i][v]; 
     if (v == u) return v; 
     for(int i=lg-1; i>=0; i--){
          if (par[i][v] != par[i][u]){
               v = par[i][v]; 
               u = par[i][u]; 
          } 
     }
     return par[0][v]; 
}

int get(int v, int k){
     int ans = 0; 
     for(int i=lg-1; i>=0; i--){
          if ((k>>i)&1){
               ans += dp[i][v]; 
               v = par[i][v]; 
          }
     }
     return ans; 
}

int getpar(int v){
     return (p[v] == v ? v : p[v] = getpar(p[v]));
}

void merge(int v, int u){
     v = getpar(v); 
     u = getpar(u); 
     if (v == u) return;
     if (siz[v] > siz[u]) swap(v,u);
     p[v] = u; 
     siz[u] += siz[v];
}

int32_t main(){
     fast_io;

     int n,k; cin >> n >> k;
     for(int i=1; i<=n; i++){
          p[i] = i; siz[i] = 1;
     }
     for(int i=1; i<=k+n-1; i++){
          cin >> t[i]; 
          if (t[i] == 'C') terminate(); 
          if (t[i] == 'S'){
               cin >> a[i] >> b[i]; 
               g[a[i]].pb({b[i],i}); 
               g[b[i]].pb({a[i],i}); 
          }
          else cin >> a[i] >> b[i]; 
     }
     tadd[1] = 1e9;
     dfs(1);
     for(int i=1; i<=k+n-1; i++){
          if (t[i] == 'S'){
               merge(a[i],b[i]); 
               continue;
          } 
          int v = a[i], u = b[i]; 
          int lc = lca(v,u); 
          bool ans = (getpar(v) == getpar(u));
          ans &= (0==get(v,h[v]-h[lc]-1));
          ans &= (get(u,h[u]-h[lc]-1) == (h[u]-h[lc])); 
          ans |= (v==u);
          cout << (ans?"yes":"no") << endl;
     }

     return 0;
}

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