oj.uz

Submission #739066

# Submission time Handle Problem Language Result Execution time Memory
739066 2023-05-09T20:06:26 Z tch1cherin Inside information (BOI21_servers) C++17
20 / 100
 3500 ms 95724 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops","omit-frame-pointer","inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

struct CustomHash {
  uint64_t operator()(size_t x) const {
    static uint64_t RANDOM = chrono::steady_clock().now().time_since_epoch().count();
    return x ^ RANDOM;
  }
};

struct fenwick {
  int size;
  vector<int> fenw, changes;

  fenwick() {}

  fenwick(int _size) : size(_size), fenw(_size + 1) {}

  void add(int i, int v) {
    for (i++; i <= size; i += i & -i) {
      fenw[i] += v;
      changes.push_back(i);
    }
  }

  int prefix_sum(int r) {
    int ans = 0;
    for (; r > 0; r -= r & -r) {
      ans += fenw[r];
    }
    return ans;
  }

  int suffix_sum(int l) {
    return prefix_sum(size) - prefix_sum(l);  
  }

  void clear() {
    for (int i : changes) {
      fenw[i] = 0;
    }
    changes.clear();
  } 
};

const int N = 120000;
vector<pair<int, int>> graph[N]; // (v, t)
vector<tuple<int, int, int, int>> Share[N]; // (a, b, t, id)
vector<tuple<int, int, int, int>> Query[N]; // (a, b, t, id) 
vector<tuple<int, int, int>> Count[N]; // (u, t, id)
int sz[N], answer[2 * N], type[N], last[N];
bool used[N];
fenwick bit;
gp_hash_table<int, int, CustomHash> s, edge;

void sizes(int u, int p) {
  sz[u] = 1;
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v]) {
      sizes(v, u);
      sz[u] += sz[v];
    }
  }
}

int centroid(int u, int p, int n) {
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v] && sz[v] > n / 2) {
      return centroid(v, u, n);
    }
  }
  return u;
}

void DFS(int u, int p, vector<int>& comp) {
  comp.push_back(u);
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v]) {
      DFS(v, u, comp);
    }
  }
}

void explore(int u, int p, int time) {
  s.insert({u, u});
  if (type[u] == 0 || type[u] == 1) {
    bit.add(edge[u], 1); 
  }
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v] && t <= time) {
      if (type[u] == 0) {
        type[v] = (last[u] == -1 ? 0 : (last[u] < t ? 1 : 2)); 
      } else if (type[u] == 1) {
        type[v] = (last[u] < t ? 1 : 3);
      } else if (type[u] == 2) {
        type[v] = (last[u] > t ? 2 : 3);
      } else {
        type[v] = 3;
      }
      last[v] = t;
      explore(v, u, time);
    }
  }
}

void find_centroids(int u, int p) {
  gp_hash_table<int, int, CustomHash> first, to;
  edge[u] = -1;
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v]) {
      sizes(v, u);
      to[v] = centroid(v, u, sz[v]);
    }
  }
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v]) {
      vector<int> comp;
      DFS(v, u, comp);
      for (int x : comp) {
        first[x] = v;
        edge[x] = t; 
      }
    }
  }
  for (auto &[k, v] : first) {
    v = to[v];
  }
  first[u] = INT_MIN;
  vector<int> D;
  for (auto [a, b, t, id] : Share[u]) {
    D.push_back(t);
  }
  for (auto [a, b, t, id] : Query[u]) {
    D.push_back(t);
  }
  for (auto [a, t, id] : Count[u]) {
    D.push_back(t);
  }
  sort(D.begin(), D.end());
  D.resize(unique(D.begin(), D.end()) - D.begin());
  int share_pos = 0, query_pos = 0, count_pos = 0;
  s.insert({u, u});
  type[u] = 0;
  last[u] = -1;
  for (int t : D) {
    while (share_pos < (int)Share[u].size() && get<2>(Share[u][share_pos]) <= t) {
      auto [a, b, _t, id] = Share[u][share_pos];
      if (first[a] == first[b]) {
        Share[first[a]].emplace_back(a, b, _t, id);  
      } 
      if (s.find(b) != s.end()) {
        swap(a, b);
      }
      if (s.find(a) != s.end()) { 
        if (type[a] == 0) {
          type[b] = (last[a] == -1 ? 0 : (last[a] < t ? 1 : 2)); 
        } else if (type[a] == 1) {
          type[b] = (last[a] < t ? 1 : 3);
        } else if (type[a] == 2) {
          type[b] = (last[a] > t ? 2 : 3);
        } else {
          type[b] = 3;
        }
        last[b] = t;
        explore(b, a, t);
      } 
      share_pos++;
    }
    while (query_pos < (int)Query[u].size() && get<2>(Query[u][query_pos]) <= t) {
      auto [a, b, _t, id] = Query[u][query_pos];
      if (a == b) {
        answer[id] = INT_MAX;
      } else if (first[a] == first[b]) {
        Query[first[a]].emplace_back(a, b, _t, id);
      } else {
        bool good = true;
        good &= s.find(a) != s.end() && s.find(b) != s.end();
        good &= type[a] <= 1;
        good &= type[b] == 0 || type[b] == 2;
        good &= edge[a] == -1 || edge[b] == -1 || edge[a] > edge[b];
        answer[id] = good ? INT_MAX : INT_MIN;
      }
      query_pos++;
    }
    while (count_pos < (int)Count[u].size() && get<1>(Count[u][count_pos]) <= t) {
      auto [a, _t, id] = Count[u][count_pos];
      if (a != u) {
        Count[first[a]].emplace_back(a, _t, id);
      }
      if (s.find(a) != s.end()) {
        if (type[a] == 0 || type[a] == 2) {
          answer[id] += bit.suffix_sum(edge[a] + 1) + 1; 
        }
      }
      count_pos++;  
    }
  }
  s.clear();
  bit.clear();
  edge.clear();
  used[u] = true;
  for (auto [v, t] : graph[u]) {
    if (v != p && !used[v]) {
      sizes(v, u);
      find_centroids(centroid(v, u, sz[v]), u);
    }
  }
}

void solve() {
  memset(used, 0, sizeof used);
  memset(answer, 0, sizeof answer);
  int n, k;
  cin >> n >> k;
  bit = fenwick(n);
  int t = 0;
  vector<tuple<int, int, int, int>> share_queries, query_queries;
  vector<tuple<int, int, int>> count_queries;
  for (int i = 0; i < n + k - 1; i++) {
    char type;
    cin >> type;
    if (type == 'S') {
      int a, b;
      cin >> a >> b;
      a--, b--;
      t++;
      graph[a].emplace_back(b, t);
      graph[b].emplace_back(a, t);
      share_queries.emplace_back(a, b, t, i);
    } else if (type == 'Q') {
      int a, d;
      cin >> a >> d;
      a--, d--;
      query_queries.emplace_back(a, d, t, i - t);
    } else {
      int d;
      cin >> d;
      d--;
      count_queries.emplace_back(d, t, i - t);
    }
  }
  sizes(0, -1);
  int c = centroid(0, -1, n);
  Share[c] = share_queries;
  Query[c] = query_queries;
  Count[c] = count_queries;
  find_centroids(c, -1);
  for (int i = 0; i < k; i++) {
    if (answer[i] == INT_MIN) {
      cout << "no\n";
    } else if (answer[i] == INT_MAX) {
      cout << "yes\n";
    } else {
      cout << answer[i] << "\n"; 
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 17868 KB Output is correct
2 Correct 63 ms 19184 KB Output is correct
3 Correct 69 ms 21700 KB Output is correct
4 Correct 77 ms 20560 KB Output is correct
5 Correct 67 ms 21224 KB Output is correct
6 Correct 46 ms 18464 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 37 ms 17868 KB Output is correct
2 Correct 63 ms 19184 KB Output is correct
3 Correct 69 ms 21700 KB Output is correct
4 Correct 77 ms 20560 KB Output is correct
5 Correct 67 ms 21224 KB Output is correct
6 Correct 46 ms 18464 KB Output is correct
7 Correct 39 ms 18540 KB Output is correct
8 Correct 91 ms 23920 KB Output is correct
9 Correct 69 ms 22084 KB Output is correct
10 Correct 117 ms 27144 KB Output is correct
11 Correct 96 ms 27740 KB Output is correct
12 Correct 47 ms 18876 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17748 KB Output is correct
2 Correct 242 ms 47404 KB Output is correct
3 Correct 229 ms 47392 KB Output is correct

Subtask #4
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 35 ms 17748 KB Output is correct
2 Correct 242 ms 47404 KB Output is correct
3 Correct 229 ms 47392 KB Output is correct
4 Correct 36 ms 17680 KB Output is correct
5 Correct 255 ms 48772 KB Output is correct
6 Correct 227 ms 46460 KB Output is correct
7 Correct 252 ms 46432 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19000 KB Output is correct
2 Correct 902 ms 93492 KB Output is correct
3 Correct 911 ms 93996 KB Output is correct
4 Correct 644 ms 78620 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 19000 KB Output is correct
2 Correct 902 ms 93492 KB Output is correct
3 Correct 911 ms 93996 KB Output is correct
4 Correct 644 ms 78620 KB Output is correct
5 Correct 49 ms 19224 KB Output is correct
6 Correct 1028 ms 95104 KB Output is correct
7 Correct 755 ms 87668 KB Output is correct
8 Correct 982 ms 95724 KB Output is correct
9 Correct 1016 ms 93932 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18756 KB Output is correct
2 Execution timed out 3560 ms 67632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 18756 KB Output is correct
2 Execution timed out 3560 ms 67632 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 19012 KB Output is correct
2 Correct 901 ms 93576 KB Output is correct
3 Correct 895 ms 93864 KB Output is correct
4 Correct 623 ms 78672 KB Output is correct
5 Correct 39 ms 18752 KB Output is correct
6 Execution timed out 3579 ms 70264 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 39 ms 19012 KB Output is correct
2 Correct 901 ms 93576 KB Output is correct
3 Correct 895 ms 93864 KB Output is correct
4 Correct 623 ms 78672 KB Output is correct
5 Correct 39 ms 18752 KB Output is correct
6 Execution timed out 3579 ms 70264 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17856 KB Output is correct
2 Correct 66 ms 19164 KB Output is correct
3 Correct 70 ms 21616 KB Output is correct
4 Correct 80 ms 20556 KB Output is correct
5 Correct 70 ms 21232 KB Output is correct
6 Correct 49 ms 18564 KB Output is correct
7 Correct 35 ms 17732 KB Output is correct
8 Correct 236 ms 47388 KB Output is correct
9 Correct 230 ms 47416 KB Output is correct
10 Correct 40 ms 18996 KB Output is correct
11 Correct 878 ms 93656 KB Output is correct
12 Correct 868 ms 93900 KB Output is correct
13 Correct 624 ms 78672 KB Output is correct
14 Correct 41 ms 18756 KB Output is correct
15 Execution timed out 3576 ms 70308 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17856 KB Output is correct
2 Correct 66 ms 19164 KB Output is correct
3 Correct 70 ms 21616 KB Output is correct
4 Correct 80 ms 20556 KB Output is correct
5 Correct 70 ms 21232 KB Output is correct
6 Correct 49 ms 18564 KB Output is correct
7 Correct 35 ms 17732 KB Output is correct
8 Correct 236 ms 47388 KB Output is correct
9 Correct 230 ms 47416 KB Output is correct
10 Correct 40 ms 18996 KB Output is correct
11 Correct 878 ms 93656 KB Output is correct
12 Correct 868 ms 93900 KB Output is correct
13 Correct 624 ms 78672 KB Output is correct
14 Correct 41 ms 18756 KB Output is correct
15 Execution timed out 3576 ms 70308 KB Time limit exceeded
16 Halted 0 ms 0 KB -