oj.uz

Submission #700910

# Submission time Handle Problem Language Result Execution time Memory
700910 2023-02-19T12:01:22 Z cig32 Inside information (BOI21_servers) C++17
50 / 100
 270 ms 119592 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 2.5e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }

int n, k;
vector<pair<int,int> > adj[MAXN];
vector<int> et;
int l[MAXN], r[MAXN], de[MAXN];
pair<int, int> spt[18][MAXN];
int par[MAXN];
int u1[MAXN],u2[MAXN];//if strictly increasing/decreasing, min [height]
int parw[MAXN];//i->par[i] weight
void dfs(int node, int prv) {
  et.push_back(node);
  par[node]=prv;
  de[node] = (prv == -1 ? 0 : de[prv] + 1);
  if(prv != -1) {
    if(prv == 1) {
      u1[node]=u2[node]=0;
    }
    else if(parw[node]<parw[prv]) {
      u2[node]=de[node]-1;
      u1[node]=u1[prv];
    }
    else {
      u1[node]=de[node]-1;
      u2[node]=u2[prv];
    }
  }
  for(auto x: adj[node]) {
    if(x.first!=prv) {
      parw[x.first]=x.second;
      dfs(x.first, node);
      et.push_back(node);
    }
  }
}
int lca(int x, int y) {
  int m1=min(l[x],l[y]), m2=max(r[x],r[y]);
  int k=32-__builtin_clz(m2-m1+1)-1;
  return min(spt[k][m1],spt[k][m2-(1<<k)+1]).second;
}
int dist(int x, int y) {
  return de[x]+de[y]-2*de[lca(x,y)];
}
int dsu[MAXN];
int binlift[18][MAXN];
int set_of(int u) {
  if(dsu[u] == u) return u;
  return dsu[u] = set_of(dsu[u]);
}
void union_(int u, int v) {
  dsu[set_of(u)] = set_of(v);
}
void solve(int tc) {
  cin >> n >> k;
  for(int i=1; i<=n; i++) dsu[i] = i;
  vector<pair<pair<int, int>, int> > vt;
  vector<int> oh;
  for(int i=0; i<n+k-1; i++) {
    char t; cin >> t;
    if(t == 'S') {
      int a, b;
      cin >> a >> b;
      adj[a].push_back({b, i});
      adj[b].push_back({a, i});
      union_(a, b);
    }
    else {
      int a, d;
      cin >> a >> d;
      if(set_of(a) == set_of(d)) oh.push_back(1);
      else oh.push_back(0);
      vt.push_back({{a, d}, i});
    }
  }
  dfs(1,-1);
  for(int i=0; i<et.size(); i++) r[et[i]]=i;
  for(int i=et.size()-1; i>=0; i--) l[et[i]]=i;
  for(int i=0; i<et.size(); i++) spt[0][i] = {de[et[i]], et[i]};
  for(int i=1; i<18; i++) {
    for(int j=0; j+(1<<i)-1<et.size(); j++) spt[i][j] = min(spt[i-1][j], spt[i-1][j+(1<<(i-1))]);
  }
  for(int i=1; i<=n; i++) binlift[0][i] = par[i];
  for(int i=1; i<18; i++) {
    for(int j=1; j<=n; j++) {
      if(binlift[i-1][j] == -1) binlift[i][j] = -1;
      else binlift[i][j] = binlift[i-1][binlift[i-1][j]];
    }
  }
  int ptr=0;
  for(auto x: vt) {
    int a=x.first.first, d=x.first.second, i=x.second;
    int dista = dist(a, lca(a,d)), distd = dist(d, lca(a,d));
    dista--, distd--;
    int aa=a, dd=d;
    for(int k=17; k>=0; k--) {
      if(dista >= (1<<k)) {
        dista -= (1<<k);
        aa=binlift[k][aa];
      }
      if(distd >= (1<<k)) {
        distd -= (1<<k);
        dd=binlift[k][dd];
      }
    }
    bool yes = 0;
    if(par[dd] == a || par[aa] == d) yes = 1;
    else if(parw[dd] < parw[aa]) yes = 1;
    if(oh[ptr] == 0) cout << "no\n";
    else if(par[a] == d || par[d] == a || a == d) cout << "yes\n";
    else if(u1[d]<=de[lca(a,d)] && u2[a]<=de[lca(a,d)] && yes) cout << "yes\n";
    else cout << "no\n";
    ptr++;
  }


}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
/*
6 6
S 1 2
Q 1 3
Q 3 1
S 1 3
Q 1 3
Q 3 1
S 1 4
S 1 5
S 1 6
Q 4 5
Q 5 4

*/

Compilation message

servers.cpp: In function 'void solve(long long int)':
servers.cpp:97:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |   for(int i=0; i<et.size(); i++) r[et[i]]=i;
      |                ~^~~~~~~~~~
servers.cpp:99:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int i=0; i<et.size(); i++) spt[0][i] = {de[et[i]], et[i]};
      |                ~^~~~~~~~~~
servers.cpp:101:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int j=0; j+(1<<i)-1<et.size(); j++) spt[i][j] = min(spt[i-1][j], spt[i-1][j+(1<<(i-1))]);
      |                  ~~~~~~~~~~^~~~~~~~~~
servers.cpp:112:44: warning: unused variable 'i' [-Wunused-variable]
  112 |     int a=x.first.first, d=x.first.second, i=x.second;
      |                                            ^

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10788 KB Output is correct
2 Correct 46 ms 14584 KB Output is correct
3 Correct 44 ms 14692 KB Output is correct
4 Correct 59 ms 14728 KB Output is correct
5 Correct 46 ms 14968 KB Output is correct
6 Correct 59 ms 14660 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10788 KB Output is correct
2 Correct 46 ms 14584 KB Output is correct
3 Correct 44 ms 14692 KB Output is correct
4 Correct 59 ms 14728 KB Output is correct
5 Correct 46 ms 14968 KB Output is correct
6 Correct 59 ms 14660 KB Output is correct
7 Incorrect 21 ms 10716 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10696 KB Output is correct
2 Correct 190 ms 110900 KB Output is correct
3 Correct 173 ms 110952 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 34 ms 10696 KB Output is correct
2 Correct 190 ms 110900 KB Output is correct
3 Correct 173 ms 110952 KB Output is correct
4 Incorrect 21 ms 10876 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10736 KB Output is correct
2 Correct 191 ms 116208 KB Output is correct
3 Correct 181 ms 116220 KB Output is correct
4 Correct 180 ms 115624 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 10736 KB Output is correct
2 Correct 191 ms 116208 KB Output is correct
3 Correct 181 ms 116220 KB Output is correct
4 Correct 180 ms 115624 KB Output is correct
5 Incorrect 20 ms 10600 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10688 KB Output is correct
2 Correct 157 ms 112624 KB Output is correct
3 Correct 182 ms 112924 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10688 KB Output is correct
2 Correct 157 ms 112624 KB Output is correct
3 Correct 182 ms 112924 KB Output is correct
4 Incorrect 20 ms 10712 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10724 KB Output is correct
2 Correct 172 ms 116312 KB Output is correct
3 Correct 218 ms 116208 KB Output is correct
4 Correct 169 ms 115696 KB Output is correct
5 Correct 37 ms 10760 KB Output is correct
6 Correct 148 ms 112616 KB Output is correct
7 Correct 232 ms 112876 KB Output is correct
8 Correct 205 ms 113616 KB Output is correct
9 Correct 204 ms 113628 KB Output is correct
10 Correct 197 ms 117036 KB Output is correct
11 Correct 270 ms 116380 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 10724 KB Output is correct
2 Correct 172 ms 116312 KB Output is correct
3 Correct 218 ms 116208 KB Output is correct
4 Correct 169 ms 115696 KB Output is correct
5 Correct 37 ms 10760 KB Output is correct
6 Correct 148 ms 112616 KB Output is correct
7 Correct 232 ms 112876 KB Output is correct
8 Correct 205 ms 113616 KB Output is correct
9 Correct 204 ms 113628 KB Output is correct
10 Correct 197 ms 117036 KB Output is correct
11 Correct 270 ms 116380 KB Output is correct
12 Incorrect 20 ms 10724 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10736 KB Output is correct
2 Correct 47 ms 14648 KB Output is correct
3 Correct 44 ms 14652 KB Output is correct
4 Correct 67 ms 14708 KB Output is correct
5 Correct 49 ms 14996 KB Output is correct
6 Correct 51 ms 14580 KB Output is correct
7 Correct 48 ms 11732 KB Output is correct
8 Correct 174 ms 111004 KB Output is correct
9 Correct 159 ms 111004 KB Output is correct
10 Correct 35 ms 11604 KB Output is correct
11 Correct 172 ms 119592 KB Output is correct
12 Correct 171 ms 119536 KB Output is correct
13 Correct 164 ms 118868 KB Output is correct
14 Correct 34 ms 11596 KB Output is correct
15 Correct 157 ms 112620 KB Output is correct
16 Correct 178 ms 112896 KB Output is correct
17 Correct 196 ms 113596 KB Output is correct
18 Correct 195 ms 113640 KB Output is correct
19 Correct 245 ms 117064 KB Output is correct
20 Correct 263 ms 116492 KB Output is correct
21 Correct 188 ms 111504 KB Output is correct
22 Correct 188 ms 111832 KB Output is correct
23 Correct 194 ms 112272 KB Output is correct
24 Correct 240 ms 112416 KB Output is correct
25 Correct 194 ms 113772 KB Output is correct
26 Correct 201 ms 112180 KB Output is correct
27 Correct 171 ms 112052 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10736 KB Output is correct
2 Correct 47 ms 14648 KB Output is correct
3 Correct 44 ms 14652 KB Output is correct
4 Correct 67 ms 14708 KB Output is correct
5 Correct 49 ms 14996 KB Output is correct
6 Correct 51 ms 14580 KB Output is correct
7 Correct 48 ms 11732 KB Output is correct
8 Correct 174 ms 111004 KB Output is correct
9 Correct 159 ms 111004 KB Output is correct
10 Correct 35 ms 11604 KB Output is correct
11 Correct 172 ms 119592 KB Output is correct
12 Correct 171 ms 119536 KB Output is correct
13 Correct 164 ms 118868 KB Output is correct
14 Correct 34 ms 11596 KB Output is correct
15 Correct 157 ms 112620 KB Output is correct
16 Correct 178 ms 112896 KB Output is correct
17 Correct 196 ms 113596 KB Output is correct
18 Correct 195 ms 113640 KB Output is correct
19 Correct 245 ms 117064 KB Output is correct
20 Correct 263 ms 116492 KB Output is correct
21 Correct 188 ms 111504 KB Output is correct
22 Correct 188 ms 111832 KB Output is correct
23 Correct 194 ms 112272 KB Output is correct
24 Correct 240 ms 112416 KB Output is correct
25 Correct 194 ms 113772 KB Output is correct
26 Correct 201 ms 112180 KB Output is correct
27 Correct 171 ms 112052 KB Output is correct
28 Incorrect 21 ms 10804 KB Extra information in the output file
29 Halted 0 ms 0 KB -