oj.uz

Submission #734671

# Submission time Handle Problem Language Result Execution time Memory
734671 2023-05-02T18:57:30 Z Sam_a17 Inside information (BOI21_servers) C++17
100 / 100
 1994 ms 74424 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;
}

int chk(int a, int b, int lst, int lim) {
  if(a == b) {
    return 1;
  }

  int ok = 0;
  for(auto i: adj[a]) {
    if(i.second > lim) continue;
    if(i.second > lst) {
      ok |= chk(i.first, b, i.second, lim);
    }
  }
  return ok;
}


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 = 1; i <= n; i++) {
    dbg(make_pair(in[i], dw[i]))
  }
  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 51 ms 34496 KB Output is correct
2 Correct 103 ms 35160 KB Output is correct
3 Correct 105 ms 35072 KB Output is correct
4 Correct 134 ms 35268 KB Output is correct
5 Correct 117 ms 35536 KB Output is correct
6 Correct 103 ms 35280 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34496 KB Output is correct
2 Correct 103 ms 35160 KB Output is correct
3 Correct 105 ms 35072 KB Output is correct
4 Correct 134 ms 35268 KB Output is correct
5 Correct 117 ms 35536 KB Output is correct
6 Correct 103 ms 35280 KB Output is correct
7 Correct 51 ms 34564 KB Output is correct
8 Correct 128 ms 36168 KB Output is correct
9 Correct 97 ms 36016 KB Output is correct
10 Correct 122 ms 36288 KB Output is correct
11 Correct 115 ms 36460 KB Output is correct
12 Correct 92 ms 36196 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 34496 KB Output is correct
2 Correct 1482 ms 59116 KB Output is correct
3 Correct 1656 ms 59248 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 65 ms 34496 KB Output is correct
2 Correct 1482 ms 59116 KB Output is correct
3 Correct 1656 ms 59248 KB Output is correct
4 Correct 55 ms 34584 KB Output is correct
5 Correct 1700 ms 60964 KB Output is correct
6 Correct 1524 ms 59916 KB Output is correct
7 Correct 1436 ms 59712 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34432 KB Output is correct
2 Correct 1865 ms 67104 KB Output is correct
3 Correct 1881 ms 67080 KB Output is correct
4 Correct 1615 ms 68752 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34432 KB Output is correct
2 Correct 1865 ms 67104 KB Output is correct
3 Correct 1881 ms 67080 KB Output is correct
4 Correct 1615 ms 68752 KB Output is correct
5 Correct 47 ms 34656 KB Output is correct
6 Correct 1896 ms 69780 KB Output is correct
7 Correct 1729 ms 71336 KB Output is correct
8 Correct 1978 ms 71768 KB Output is correct
9 Correct 1994 ms 71756 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 34432 KB Output is correct
2 Correct 1444 ms 59948 KB Output is correct
3 Correct 1512 ms 58508 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 34432 KB Output is correct
2 Correct 1444 ms 59948 KB Output is correct
3 Correct 1512 ms 58508 KB Output is correct
4 Correct 51 ms 34628 KB Output is correct
5 Correct 1463 ms 62308 KB Output is correct
6 Correct 1531 ms 60496 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34464 KB Output is correct
2 Correct 1590 ms 67448 KB Output is correct
3 Correct 1526 ms 67088 KB Output is correct
4 Correct 1363 ms 68832 KB Output is correct
5 Correct 58 ms 34488 KB Output is correct
6 Correct 1442 ms 59992 KB Output is correct
7 Correct 1424 ms 58724 KB Output is correct
8 Correct 1460 ms 59496 KB Output is correct
9 Correct 1560 ms 59280 KB Output is correct
10 Correct 1573 ms 64440 KB Output is correct
11 Correct 1551 ms 63936 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 34464 KB Output is correct
2 Correct 1590 ms 67448 KB Output is correct
3 Correct 1526 ms 67088 KB Output is correct
4 Correct 1363 ms 68832 KB Output is correct
5 Correct 58 ms 34488 KB Output is correct
6 Correct 1442 ms 59992 KB Output is correct
7 Correct 1424 ms 58724 KB Output is correct
8 Correct 1460 ms 59496 KB Output is correct
9 Correct 1560 ms 59280 KB Output is correct
10 Correct 1573 ms 64440 KB Output is correct
11 Correct 1551 ms 63936 KB Output is correct
12 Correct 48 ms 35504 KB Output is correct
13 Correct 1579 ms 72536 KB Output is correct
14 Correct 1507 ms 74420 KB Output is correct
15 Correct 1543 ms 71768 KB Output is correct
16 Correct 1564 ms 71672 KB Output is correct
17 Correct 51 ms 35464 KB Output is correct
18 Correct 1414 ms 65276 KB Output is correct
19 Correct 1435 ms 63520 KB Output is correct
20 Correct 1494 ms 64852 KB Output is correct
21 Correct 1453 ms 64880 KB Output is correct
22 Correct 1582 ms 69316 KB Output is correct
23 Correct 1636 ms 68704 KB Output is correct
24 Correct 1670 ms 68296 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34432 KB Output is correct
2 Correct 101 ms 35192 KB Output is correct
3 Correct 97 ms 35092 KB Output is correct
4 Correct 108 ms 35216 KB Output is correct
5 Correct 94 ms 35468 KB Output is correct
6 Correct 94 ms 35280 KB Output is correct
7 Correct 52 ms 34432 KB Output is correct
8 Correct 1277 ms 59272 KB Output is correct
9 Correct 1261 ms 59144 KB Output is correct
10 Correct 43 ms 34500 KB Output is correct
11 Correct 1461 ms 67020 KB Output is correct
12 Correct 1438 ms 67136 KB Output is correct
13 Correct 1349 ms 68840 KB Output is correct
14 Correct 56 ms 34484 KB Output is correct
15 Correct 1309 ms 59948 KB Output is correct
16 Correct 1401 ms 58560 KB Output is correct
17 Correct 1439 ms 59448 KB Output is correct
18 Correct 1442 ms 59380 KB Output is correct
19 Correct 1439 ms 64528 KB Output is correct
20 Correct 1556 ms 64152 KB Output is correct
21 Correct 1273 ms 63188 KB Output is correct
22 Correct 1302 ms 62664 KB Output is correct
23 Correct 1364 ms 62084 KB Output is correct
24 Correct 1347 ms 62188 KB Output is correct
25 Correct 1518 ms 70060 KB Output is correct
26 Correct 1441 ms 61636 KB Output is correct
27 Correct 1379 ms 61560 KB Output is correct

Subtask #12
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 51 ms 34432 KB Output is correct
2 Correct 101 ms 35192 KB Output is correct
3 Correct 97 ms 35092 KB Output is correct
4 Correct 108 ms 35216 KB Output is correct
5 Correct 94 ms 35468 KB Output is correct
6 Correct 94 ms 35280 KB Output is correct
7 Correct 52 ms 34432 KB Output is correct
8 Correct 1277 ms 59272 KB Output is correct
9 Correct 1261 ms 59144 KB Output is correct
10 Correct 43 ms 34500 KB Output is correct
11 Correct 1461 ms 67020 KB Output is correct
12 Correct 1438 ms 67136 KB Output is correct
13 Correct 1349 ms 68840 KB Output is correct
14 Correct 56 ms 34484 KB Output is correct
15 Correct 1309 ms 59948 KB Output is correct
16 Correct 1401 ms 58560 KB Output is correct
17 Correct 1439 ms 59448 KB Output is correct
18 Correct 1442 ms 59380 KB Output is correct
19 Correct 1439 ms 64528 KB Output is correct
20 Correct 1556 ms 64152 KB Output is correct
21 Correct 1273 ms 63188 KB Output is correct
22 Correct 1302 ms 62664 KB Output is correct
23 Correct 1364 ms 62084 KB Output is correct
24 Correct 1347 ms 62188 KB Output is correct
25 Correct 1518 ms 70060 KB Output is correct
26 Correct 1441 ms 61636 KB Output is correct
27 Correct 1379 ms 61560 KB Output is correct
28 Correct 49 ms 35516 KB Output is correct
29 Correct 95 ms 37348 KB Output is correct
30 Correct 94 ms 37160 KB Output is correct
31 Correct 100 ms 37380 KB Output is correct
32 Correct 98 ms 37596 KB Output is correct
33 Correct 93 ms 37248 KB Output is correct
34 Correct 51 ms 35456 KB Output is correct
35 Correct 1265 ms 63748 KB Output is correct
36 Correct 1200 ms 61552 KB Output is correct
37 Correct 1210 ms 61860 KB Output is correct
38 Correct 44 ms 35448 KB Output is correct
39 Correct 1470 ms 72560 KB Output is correct
40 Correct 1373 ms 74424 KB Output is correct
41 Correct 1469 ms 71996 KB Output is correct
42 Correct 1480 ms 71884 KB Output is correct
43 Correct 48 ms 35456 KB Output is correct
44 Correct 1374 ms 65388 KB Output is correct
45 Correct 1386 ms 63532 KB Output is correct
46 Correct 1428 ms 64900 KB Output is correct
47 Correct 1465 ms 64892 KB Output is correct
48 Correct 1577 ms 69228 KB Output is correct
49 Correct 1647 ms 68852 KB Output is correct
50 Correct 1602 ms 68380 KB Output is correct
51 Correct 1224 ms 63484 KB Output is correct
52 Correct 1207 ms 62584 KB Output is correct
53 Correct 1212 ms 62148 KB Output is correct
54 Correct 1215 ms 62736 KB Output is correct
55 Correct 1242 ms 62744 KB Output is correct
56 Correct 1339 ms 63356 KB Output is correct
57 Correct 1459 ms 69692 KB Output is correct
58 Correct 1538 ms 63336 KB Output is correct
59 Correct 1451 ms 62280 KB Output is correct