oj.uz

Submission #899005

# Submission time Handle Problem Language Result Execution time Memory
899005 2024-01-05T10:44:37 Z Iliya_ Inside information (BOI21_servers) C++17
0 / 100
 37 ms 65660 KB 
//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

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 65104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 65104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 65104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 65104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 65228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 65228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 65660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 65660 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 65108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 65108 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 65104 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 65104 KB Output isn't correct
2 Halted 0 ms 0 KB -