oj.uz

Submission #734669

# Submission time Handle Problem Language Result Execution time Memory
734669 2023-05-02T18:56:46 Z Sam_a17 Inside information (BOI21_servers) C++17
35 / 100
 3500 ms 74416 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) {

      return chk(a, b, -1, tt);
      // 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 55 ms 34452 KB Output is correct
2 Correct 95 ms 35192 KB Output is correct
3 Correct 121 ms 35116 KB Output is correct
4 Correct 105 ms 35328 KB Output is correct
5 Correct 110 ms 35620 KB Output is correct
6 Correct 100 ms 35256 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 34452 KB Output is correct
2 Correct 95 ms 35192 KB Output is correct
3 Correct 121 ms 35116 KB Output is correct
4 Correct 105 ms 35328 KB Output is correct
5 Correct 110 ms 35620 KB Output is correct
6 Correct 100 ms 35256 KB Output is correct
7 Correct 49 ms 34604 KB Output is correct
8 Correct 96 ms 36196 KB Output is correct
9 Correct 96 ms 36044 KB Output is correct
10 Correct 103 ms 36300 KB Output is correct
11 Correct 97 ms 36556 KB Output is correct
12 Correct 98 ms 36144 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 34480 KB Output is correct
2 Correct 1365 ms 59204 KB Output is correct
3 Correct 1307 ms 59120 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 55 ms 34480 KB Output is correct
2 Correct 1365 ms 59204 KB Output is correct
3 Correct 1307 ms 59120 KB Output is correct
4 Correct 53 ms 34640 KB Output is correct
5 Correct 1312 ms 60992 KB Output is correct
6 Correct 1280 ms 59936 KB Output is correct
7 Correct 1242 ms 59760 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 34444 KB Output is correct
2 Correct 1526 ms 67076 KB Output is correct
3 Correct 1521 ms 67144 KB Output is correct
4 Correct 1349 ms 68848 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 34444 KB Output is correct
2 Correct 1526 ms 67076 KB Output is correct
3 Correct 1521 ms 67144 KB Output is correct
4 Correct 1349 ms 68848 KB Output is correct
5 Correct 45 ms 35568 KB Output is correct
6 Correct 1542 ms 72460 KB Output is correct
7 Execution timed out 3564 ms 74416 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 34408 KB Output is correct
2 Correct 1434 ms 59772 KB Output is correct
3 Correct 1419 ms 58532 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 34408 KB Output is correct
2 Correct 1434 ms 59772 KB Output is correct
3 Correct 1419 ms 58532 KB Output is correct
4 Correct 47 ms 34564 KB Output is correct
5 Correct 1497 ms 62384 KB Output is correct
6 Correct 1503 ms 60600 KB Output is correct

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34432 KB Output is correct
2 Correct 1526 ms 67144 KB Output is correct
3 Correct 1502 ms 67316 KB Output is correct
4 Correct 1429 ms 68776 KB Output is correct
5 Correct 58 ms 35336 KB Output is correct
6 Correct 1366 ms 63308 KB Output is correct
7 Correct 1509 ms 61808 KB Output is correct
8 Correct 1505 ms 62764 KB Output is correct
9 Correct 1782 ms 62616 KB Output is correct
10 Correct 2943 ms 67820 KB Output is correct
11 Execution timed out 3533 ms 66968 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 34432 KB Output is correct
2 Correct 1526 ms 67144 KB Output is correct
3 Correct 1502 ms 67316 KB Output is correct
4 Correct 1429 ms 68776 KB Output is correct
5 Correct 58 ms 35336 KB Output is correct
6 Correct 1366 ms 63308 KB Output is correct
7 Correct 1509 ms 61808 KB Output is correct
8 Correct 1505 ms 62764 KB Output is correct
9 Correct 1782 ms 62616 KB Output is correct
10 Correct 2943 ms 67820 KB Output is correct
11 Execution timed out 3533 ms 66968 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 34432 KB Output is correct
2 Correct 122 ms 35124 KB Output is correct
3 Correct 108 ms 35040 KB Output is correct
4 Correct 122 ms 35232 KB Output is correct
5 Correct 136 ms 35472 KB Output is correct
6 Correct 142 ms 35200 KB Output is correct
7 Correct 52 ms 34452 KB Output is correct
8 Correct 1640 ms 59248 KB Output is correct
9 Correct 1630 ms 59124 KB Output is correct
10 Correct 57 ms 34400 KB Output is correct
11 Correct 1886 ms 67088 KB Output is correct
12 Correct 1759 ms 67048 KB Output is correct
13 Correct 1661 ms 68780 KB Output is correct
14 Correct 78 ms 35384 KB Output is correct
15 Correct 1672 ms 63052 KB Output is correct
16 Correct 1726 ms 61820 KB Output is correct
17 Correct 1786 ms 62840 KB Output is correct
18 Correct 1852 ms 62504 KB Output is correct
19 Correct 2737 ms 67836 KB Output is correct
20 Execution timed out 3557 ms 67124 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 34432 KB Output is correct
2 Correct 122 ms 35124 KB Output is correct
3 Correct 108 ms 35040 KB Output is correct
4 Correct 122 ms 35232 KB Output is correct
5 Correct 136 ms 35472 KB Output is correct
6 Correct 142 ms 35200 KB Output is correct
7 Correct 52 ms 34452 KB Output is correct
8 Correct 1640 ms 59248 KB Output is correct
9 Correct 1630 ms 59124 KB Output is correct
10 Correct 57 ms 34400 KB Output is correct
11 Correct 1886 ms 67088 KB Output is correct
12 Correct 1759 ms 67048 KB Output is correct
13 Correct 1661 ms 68780 KB Output is correct
14 Correct 78 ms 35384 KB Output is correct
15 Correct 1672 ms 63052 KB Output is correct
16 Correct 1726 ms 61820 KB Output is correct
17 Correct 1786 ms 62840 KB Output is correct
18 Correct 1852 ms 62504 KB Output is correct
19 Correct 2737 ms 67836 KB Output is correct
20 Execution timed out 3557 ms 67124 KB Time limit exceeded
21 Halted 0 ms 0 KB -