oj.uz

Submission #734672

# Submission time Handle Problem Language Result Execution time Memory
734672 2023-05-02T19:01:16 Z Sam_a17 Inside information (BOI21_servers) C++17
100 / 100
 590 ms 67284 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include "temp.cpp"
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define blt(x) __builtin_popcount(x)
 
#define pb push_back
#define popf pop_front
#define popb pop_back
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(long double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(T v[],V n) {cerr << "["; for(int i = 0; i < n; i++) {print(v[i]); cerr << " "; } cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for grid problems
int dx[8] = {-1,0,1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  }
}
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 4e5 + 10, inf = 1e9 + 10, LOG = 21;
vector<pair<int, int>> adj[N];
long long ans[N], sz[N];
vector<int> qq[N], qx[N];
bool pp[N], used[N];
int n, q, compSize;

int up[N][LOG], in[N], dw[N];
int par[N], depths[N];

struct query {
  char type;
  int x, y;
};

vector<query> queries;

void dfsik(int node, int parent) {
  for(auto i: adj[node]) {
    if(i.first == parent) continue;

    up[i.first][0] = node;
    for(int j = 1; j < LOG; j++) {
      up[i.first][j] = up[up[i.first][j - 1]][j - 1];
    }

    par[i.first] = i.second;
    depths[i.first] = depths[node] + 1;
    dfsik(i.first, node);
  }
}

void dfs1(int node, int parent) {
  for(auto i: adj[node]) {
    if(i.first == parent) continue;

    if(i.second < par[node]) {
      in[i.first] = in[node] + 1;
    } else {
      in[i.first] = 1;
    }

    if(i.second > par[node]) {
      dw[i.first] = dw[node] + 1;
    } else {
      dw[i.first] = 1;
    }

    dfs1(i.first, node);
  }
}

int lca(int a, int b) {
  if(a == b) {
    return a;
  }

  if(depths[a] > depths[b]) {
    swap(a, b);
  }

  int delta = depths[b] - depths[a];
  for(int i = 0; i < LOG; i++) {
    if(delta & (1 << i)) {
      b = up[b][i];
    }
  }

  if(a == b) {
    return a;
  }

  for(int i = LOG - 1; i >= 0; i--) {
    if(up[a][i] != up[b][i]) {
      a = up[a][i], b = up[b][i];
    }
  }
  return up[a][0];
}

int go_up(int a, int b) {
  for(int i = 0; i < LOG; i++) {
    if(b & (1 << i)) {
      a = up[a][i];
    }
  }
  return a;
}

bool check(int a, int b, int tt) {
  if(a == b) {
    return true;
  }

  int lc = lca(a, b), ok = 1;
  int first = depths[a] - depths[lc];
  if(in[a] < first) {
    ok = 0;
  }

  int second = depths[b] - depths[lc];
  if(dw[b] < second) {
    ok = 0;
  }

  if(!ok) {
    return ok;
  }

  if(lc == a || lc == b) {
    if(lc == a && par[b] > tt) {
      ok = 0;
    } else if(lc == b) {
      int na = go_up(a, first - 1);
      if(par[na] > tt) {
        ok = 0;
      }
    }
  } else {
    int na = go_up(a, first - 1);
    int nb = go_up(b, second - 1);

    if(par[na] > par[nb]) {
      ok = 0;
    }

    if(par[b] > tt) {
      ok = 0;
    }

    // if(ok) {
      // return chk(a, b, -1, tt);
    // }
  }

  return ok;
}


void dfs_sz(int node, int parent) {
  sz[node] = 1;
  compSize++;
  for(auto i: adj[node]) {
    if(i.first == parent || used[i.first]) continue;
    dfs_sz(i.first, node);
    sz[node] += sz[i.first];
  }
}

int centroid(int u, int parent) {
  for(auto i: adj[u]) {
    if(i.first == parent || used[i.first]) continue;
    if(sz[i.first] * 2 > compSize) {
      return centroid(i.first, u);
    }
  }
  return u;
}


// bit
struct fenwick {
  int size;
  vector<long long> tree; 

  void init(int size_) {
    tree.assign(size_ + 2, 0);
    size = size_;
  }

  void upd(int u, long long v) {
    while(u <= size) {
      tree[u] += v;
      u += u & (-u);
    }
  }

  long long qry(int u) {
    long long sum = 0;
    while(u > 0) {
      sum += tree[u];
      u -= u & (-u); // lsb
    }
    return sum;
  }

  long long sum(int l, int r) {
    if(l > r) {
      return 0;
    }
    return qry(r) - qry(l - 1);
  }

} ft_inc, ft_dec;

int get_centroid(int u) {
  compSize = 0;
  dfs_sz(u, 0);
  int center = centroid(u, 0);
  return center;
}

vector<int> which_dec;
vector<pair<int, int>> curr_inc, curr_dec;

bool rev = false;

void solve(int node, int parent, int incr, int decr, int lst, int st) {
  if(parent) {
    if(incr != -1) {
      curr_inc.push_back({st, node});
    }

    if(decr != -1) {
      curr_dec.push_back({lst, node});
      which_dec.push_back(lst);
    }
  }

  for(auto i: adj[node]) {
    if(i.first == parent || used[i.first]) continue;

    if(!parent) {
      solve(i.first, node, i.second, i.second, i.second, i.second);
    } else {
      int new_incr = -1, new_decr = -1;
      if(i.second < lst && incr != -1) {
        new_incr = i.second;
      }

      if(i.second > lst && decr != -1) {
        new_decr = i.second;
      }

      solve(i.first, node, new_incr, new_decr, i.second, st);
    }

    if(parent) continue;
    for(auto j: curr_inc) {
      for(auto k: qq[j.second]) {
        if(k < j.first) continue;
        ans[k - 1]++;
        ans[k - 1] += ft_dec.sum(j.first + 1, k);
      }
    }

    for(auto j: curr_dec) {
      ft_dec.upd(j.first, 1);
    }

    //
    curr_inc.clear();
    curr_dec.clear();
  }
}

void centroid_decomposition() {
  queue<int> q;
  q.push(1);

  while(!q.empty()) {
    auto u = q.front();
    q.pop();

    int center = get_centroid(u);
    solve(center, 0, -1, -1, -1, -1);

    for(auto k: qq[center]) {
      ans[k - 1] += ft_dec.sum(1, k - 1);
    }

    for(auto i: which_dec) {
      ft_dec.upd(i, -1);
    }
    which_dec.clear();

    used[center] = true;
    for(auto i: adj[center]) {
      if(used[i.first]) continue;
      q.push(i.first);
    }
  }
}

bool cmp(pair<int, int>& a, pair<int, int>& b) {
  return a.second > b.second;
}

void solve_() {
  cin >> n >> q;
  
  q += n - 1;

  ft_dec.init(N);

  for(int i = 0; i < q; i++) {
    char type; cin >> type;
    int x, y;
    if(type == 'S') {
      cin >> x >> y;
      adj[x].push_back({y, i + 1});
      adj[y].push_back({x, i + 1});
      queries.push_back({type, x, y});
    } else if(type == 'Q') {
      cin >> x >> y, pp[i] = true;
      qx[x].push_back(y);
      queries.push_back({type, x, y});
    } else {
      cin >> x, pp[i] = true;
      qq[x].push_back(i + 1);
      queries.push_back({type, x, -1});
    }
  }

  for(int i = 1; i <= n; i++) {
    sort(all(adj[i]), cmp);
  }


  dfsik(1, 0);
  dfs1(1, 0);
  centroid_decomposition();

  for(int i = 0; i < q; i++) {
    if(!pp[i]) continue;
    if(queries[i].type == 'Q') {
      if(check(queries[i].y, queries[i].x, i + 1)) {
        cout << "yes" << '\n';
      } else {
        cout << "no" << '\n';
      }
    } else {
      cout << ans[i] + 1 << '\n';
    }
  }
}
 
int main() {
  setIO();
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1;
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

servers.cpp: In function 'void setIO(std::string)':
servers.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 34440 KB Output is correct
2 Correct 60 ms 35136 KB Output is correct
3 Correct 58 ms 34904 KB Output is correct
4 Correct 69 ms 35144 KB Output is correct
5 Correct 58 ms 35364 KB Output is correct
6 Correct 64 ms 35180 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 48 ms 34440 KB Output is correct
2 Correct 60 ms 35136 KB Output is correct
3 Correct 58 ms 34904 KB Output is correct
4 Correct 69 ms 35144 KB Output is correct
5 Correct 58 ms 35364 KB Output is correct
6 Correct 64 ms 35180 KB Output is correct
7 Correct 49 ms 34668 KB Output is correct
8 Correct 61 ms 36072 KB Output is correct
9 Correct 64 ms 35972 KB Output is correct
10 Correct 61 ms 36164 KB Output is correct
11 Correct 58 ms 36392 KB Output is correct
12 Correct 57 ms 36060 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 34468 KB Output is correct
2 Correct 227 ms 55572 KB Output is correct
3 Correct 216 ms 55704 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 60 ms 34468 KB Output is correct
2 Correct 227 ms 55572 KB Output is correct
3 Correct 216 ms 55704 KB Output is correct
4 Correct 53 ms 34660 KB Output is correct
5 Correct 223 ms 57356 KB Output is correct
6 Correct 128 ms 56208 KB Output is correct
7 Correct 165 ms 56140 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 34436 KB Output is correct
2 Correct 508 ms 63504 KB Output is correct
3 Correct 471 ms 63644 KB Output is correct
4 Correct 327 ms 64700 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 34436 KB Output is correct
2 Correct 508 ms 63504 KB Output is correct
3 Correct 471 ms 63644 KB Output is correct
4 Correct 327 ms 64700 KB Output is correct
5 Correct 47 ms 34648 KB Output is correct
6 Correct 544 ms 65960 KB Output is correct
7 Correct 327 ms 67284 KB Output is correct
8 Correct 543 ms 65624 KB Output is correct
9 Correct 450 ms 65460 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 34480 KB Output is correct
2 Correct 249 ms 56044 KB Output is correct
3 Correct 308 ms 54880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 34480 KB Output is correct
2 Correct 249 ms 56044 KB Output is correct
3 Correct 308 ms 54880 KB Output is correct
4 Correct 51 ms 34652 KB Output is correct
5 Correct 328 ms 58620 KB Output is correct
6 Correct 370 ms 56920 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 34532 KB Output is correct
2 Correct 498 ms 63500 KB Output is correct
3 Correct 463 ms 63448 KB Output is correct
4 Correct 315 ms 64736 KB Output is correct
5 Correct 52 ms 34472 KB Output is correct
6 Correct 254 ms 56112 KB Output is correct
7 Correct 395 ms 55020 KB Output is correct
8 Correct 369 ms 55864 KB Output is correct
9 Correct 376 ms 55672 KB Output is correct
10 Correct 474 ms 60580 KB Output is correct
11 Correct 552 ms 59816 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 34532 KB Output is correct
2 Correct 498 ms 63500 KB Output is correct
3 Correct 463 ms 63448 KB Output is correct
4 Correct 315 ms 64736 KB Output is correct
5 Correct 52 ms 34472 KB Output is correct
6 Correct 254 ms 56112 KB Output is correct
7 Correct 395 ms 55020 KB Output is correct
8 Correct 369 ms 55864 KB Output is correct
9 Correct 376 ms 55672 KB Output is correct
10 Correct 474 ms 60580 KB Output is correct
11 Correct 552 ms 59816 KB Output is correct
12 Correct 43 ms 34560 KB Output is correct
13 Correct 450 ms 65896 KB Output is correct
14 Correct 305 ms 67264 KB Output is correct
15 Correct 470 ms 65448 KB Output is correct
16 Correct 478 ms 65440 KB Output is correct
17 Correct 59 ms 34556 KB Output is correct
18 Correct 314 ms 58672 KB Output is correct
19 Correct 404 ms 56984 KB Output is correct
20 Correct 439 ms 58268 KB Output is correct
21 Correct 365 ms 58232 KB Output is correct
22 Correct 491 ms 62504 KB Output is correct
23 Correct 580 ms 61904 KB Output is correct
24 Correct 589 ms 60884 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34492 KB Output is correct
2 Correct 66 ms 35076 KB Output is correct
3 Correct 65 ms 35016 KB Output is correct
4 Correct 70 ms 35120 KB Output is correct
5 Correct 63 ms 35404 KB Output is correct
6 Correct 62 ms 35084 KB Output is correct
7 Correct 51 ms 34464 KB Output is correct
8 Correct 230 ms 55508 KB Output is correct
9 Correct 210 ms 55484 KB Output is correct
10 Correct 46 ms 34416 KB Output is correct
11 Correct 407 ms 63444 KB Output is correct
12 Correct 478 ms 63500 KB Output is correct
13 Correct 285 ms 64696 KB Output is correct
14 Correct 53 ms 34444 KB Output is correct
15 Correct 244 ms 56060 KB Output is correct
16 Correct 360 ms 55032 KB Output is correct
17 Correct 337 ms 55796 KB Output is correct
18 Correct 333 ms 55656 KB Output is correct
19 Correct 458 ms 60536 KB Output is correct
20 Correct 472 ms 59808 KB Output is correct
21 Correct 252 ms 55912 KB Output is correct
22 Correct 257 ms 55600 KB Output is correct
23 Correct 302 ms 55172 KB Output is correct
24 Correct 260 ms 55272 KB Output is correct
25 Correct 444 ms 62920 KB Output is correct
26 Correct 311 ms 54392 KB Output is correct
27 Correct 301 ms 54084 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 54 ms 34492 KB Output is correct
2 Correct 66 ms 35076 KB Output is correct
3 Correct 65 ms 35016 KB Output is correct
4 Correct 70 ms 35120 KB Output is correct
5 Correct 63 ms 35404 KB Output is correct
6 Correct 62 ms 35084 KB Output is correct
7 Correct 51 ms 34464 KB Output is correct
8 Correct 230 ms 55508 KB Output is correct
9 Correct 210 ms 55484 KB Output is correct
10 Correct 46 ms 34416 KB Output is correct
11 Correct 407 ms 63444 KB Output is correct
12 Correct 478 ms 63500 KB Output is correct
13 Correct 285 ms 64696 KB Output is correct
14 Correct 53 ms 34444 KB Output is correct
15 Correct 244 ms 56060 KB Output is correct
16 Correct 360 ms 55032 KB Output is correct
17 Correct 337 ms 55796 KB Output is correct
18 Correct 333 ms 55656 KB Output is correct
19 Correct 458 ms 60536 KB Output is correct
20 Correct 472 ms 59808 KB Output is correct
21 Correct 252 ms 55912 KB Output is correct
22 Correct 257 ms 55600 KB Output is correct
23 Correct 302 ms 55172 KB Output is correct
24 Correct 260 ms 55272 KB Output is correct
25 Correct 444 ms 62920 KB Output is correct
26 Correct 311 ms 54392 KB Output is correct
27 Correct 301 ms 54084 KB Output is correct
28 Correct 49 ms 34664 KB Output is correct
29 Correct 57 ms 36092 KB Output is correct
30 Correct 54 ms 35964 KB Output is correct
31 Correct 66 ms 36164 KB Output is correct
32 Correct 69 ms 36400 KB Output is correct
33 Correct 53 ms 36080 KB Output is correct
34 Correct 50 ms 34688 KB Output is correct
35 Correct 203 ms 57336 KB Output is correct
36 Correct 125 ms 56292 KB Output is correct
37 Correct 130 ms 56080 KB Output is correct
38 Correct 48 ms 34572 KB Output is correct
39 Correct 431 ms 66080 KB Output is correct
40 Correct 367 ms 67268 KB Output is correct
41 Correct 465 ms 65524 KB Output is correct
42 Correct 402 ms 65408 KB Output is correct
43 Correct 49 ms 34632 KB Output is correct
44 Correct 320 ms 58608 KB Output is correct
45 Correct 368 ms 56924 KB Output is correct
46 Correct 365 ms 58212 KB Output is correct
47 Correct 420 ms 58300 KB Output is correct
48 Correct 501 ms 62496 KB Output is correct
49 Correct 573 ms 61836 KB Output is correct
50 Correct 590 ms 60860 KB Output is correct
51 Correct 144 ms 56848 KB Output is correct
52 Correct 156 ms 56296 KB Output is correct
53 Correct 138 ms 56056 KB Output is correct
54 Correct 149 ms 56296 KB Output is correct
55 Correct 141 ms 56440 KB Output is correct
56 Correct 269 ms 56672 KB Output is correct
57 Correct 464 ms 63100 KB Output is correct
58 Correct 519 ms 56908 KB Output is correct
59 Correct 359 ms 55180 KB Output is correct