제출 #739051

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739051		tch1cherin	Inside information (BOI21_servers)	C++17	87.50 / 100	3568 ms	108344 KiB

servers

#include <bits/stdc++.h>
using namespace std;

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;
set<int> s;
map<int, int> 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);
  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) {
  map<int, int> 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);
  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.count(b)) {
        swap(a, b);
      }
      if (s.count(a)) { 
        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.count(a) && s.count(b);
        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.count(a)) {
        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
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5