Submission #1009401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009401		somefjord	Drivers (BOI24_drivers)	C++17	100 / 100	249 ms	15172 KiB

Main

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

struct DSU {
  vector<int> parent;
  vector<int> rank;

  DSU(int n) : parent(n, -1), rank(n, 0) {}

  void unite(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v)
      return;
    if (rank[v] > rank[u])
      swap(u, v);
    rank[u]++;
    parent[v] = u;
  }

  int find(int u) {
    if (parent[u] == -1)
      return u;
    return parent[u] = find(parent[u]);
  }
};

int main() {
  int n, m, u;
  cin >> n >> m >> u;

  vector<array<int, 3>> roads(m);
  int x, y, t;
  for (auto &r : roads) {
    cin >> x >> y >> t;
    r = {t, x, y};
  }

  sort(roads.begin(), roads.end());

  vector<array<int, 4>> queries(u);
  int a, b, p;
  for (int i = 0; i < u; ++i) {
    cin >> a >> b >> p;
    queries[i] = {p, a, b, i};
  }

  sort(queries.begin(), queries.end());

  DSU dsu(n + 1);
  vector<bool> answer(u);

  int roadcursor = 0;
  for (auto [p, a, b, i] : queries) {
    for (; roadcursor < m; ++roadcursor) {
      auto [t, x, y] = roads[roadcursor];
      if (t > p)
        break;
      dsu.unite(x, y);
    }
    if (dsu.find(a) == dsu.find(b))
      answer[i] = true;
  }

  for (auto b : answer)
    cout << (b ? "TAIP" : "NE") << '\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 23 / 23
• Subtask 5: 45 / 45