Submission #556867

#	Time	Username	Problem	Language	Result	Execution time	Memory
556867		Soumya1	Inside information (BOI21_servers)	C++17	5 / 100	1695 ms	2540 KiB

servers

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
const int mxN = 4005;
vector<tuple<int, int, int>> queries;
vector<pair<int, int>> ad[mxN];
bool vis[mxN];
int cnt = 0;
void dfs(int u, int p,  int last, int lim) {
  vis[u] = true;
  cnt++;
  for (auto [v, ee] : ad[u]) {
    if (ee >= lim || v == p || last > ee) continue;
    dfs(v, u, ee, lim);
  }
}
void testCase() {
  int n, q;
  cin >> n >> q;
  int cur_edge = 0;
  for (int i = 0; i < n + q - 1; i++) {
    char c;
    cin >> c;
    if (c == 'S') {
      int u, v;
      cin >> u >> v;
      ad[u].push_back({v,  cur_edge});
      ad[v].push_back({u, cur_edge});
      cur_edge++;
    } else if (c == 'Q') {
      int u, v;
      cin >> u >> v;
      queries.push_back({u, v, cur_edge});
    } else {
      int u;
      cin >> u;
      queries.push_back({0, u, cur_edge});
    }
  }
  for (auto [u, v, ee] : queries) {
    dfs(v, -1, -1, ee);
    if (u) {
      cout << (vis[u] ? "yes\n" : "no\n");
    } else {
      cout << cnt << "\n";
    }
    memset(vis, 0, sizeof vis);
    cnt = 0;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5