oj.uz

Submission #1118478

# Submission time Handle Problem Language Result Execution time Memory
1118478 2024-11-25T14:30:31 Z quanquai Drivers (BOI24_drivers) C++11
0 / 100
 1 ms 2396 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2396 KB Output isn't correct
2 Halted 0 ms 0 KB -