제출 #1118478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1118478		quanquai	Drivers (BOI24_drivers)	C++11	0 / 100	1 ms	2396 KiB

Main

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

#define i64 long long
#define i32 int
#define all(v) (v).begin(), (v).end()
#define task "drivers"

const int N = 2e5 + 123;

int n, m, q;
int ans[N];
array<int, 3> edge[N];
array<int, 4> que[N];

struct DSU {
   vector<int> par, sz;
   DSU(int n) : par(n + 1), sz(n + 1) {
      for (int i = 1; i <= n; i++) {
         par[i] = i;
         sz[i] = 1;
      }
   }
   int get(int u) {
      return (u == par[u] ? par[u] : par[u] = get(par[u]));
   }
   void join(int u, int v) {
      u = get(u);
      v = get(v);
      if (u == v) return;
      if (sz[u] < sz[v]) swap(u, v);
      par[v] = par[u];
      sz[u] += sz[v];
   }
   bool same(int u, int v) {
      u = get(u);
      v = get(v);
      return (u == v);
   }
};

int main() {
   ios::sync_with_stdio(false);
   cin.tie(0);

   cin >> n >> m >> q;
   for (int i = 0; i < m; i++) {
      int u, v, w;
      cin >> u >> v >> w;
      edge[i] = {w, u, v};
   }
   for (int i = 0; i < q; i++) {
      cin >> que[i][1] >> que[i][2] >> que[i][0];
      que[i][3] = i;
   }
   sort(que, que + q);
   sort(edge, edge + m);
   int j = 0;
   DSU dsu(n);
   for (int i = 0; i < q; i++) {
      while (j < q && edge[j][0] <= que[i][2]) {
         int u = edge[j][1];
         int v = edge[j][2];
         dsu.join(u, v);
         j++;
      }
      if (dsu.same(que[i][1], que[i][2])) {
         ans[que[i][3]] = 1;
      } else {
         ans[que[i][3]] = 0;
      }
   }
   for (int i = 0; i < q; i++) {
      if (ans[i]) {
         cout << "TAIP\n";
      } else {
         cout << "NE\n";
      }
   }

  return 0;
}

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