Submission #1085878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085878		anastasiskolio	Drivers (BOI24_drivers)	C++14	100 / 100	158 ms	21548 KiB

Main

#include <bits/stdc++.h>
#define MAXN 200000
#define MAXM 200000
#define MAXU 200000
using namespace std;

vector<array<int, 3>> edges(MAXM);
vector<array<int, 4>> queries(MAXU);
vector<int> parent(MAXN), comp_size(MAXN);
vector<string> ans(MAXU);
int N, M, U;

void disjointSets() {
  for (int a = 0; a < N; a++) {
    parent[a] = a;
    comp_size[a] = 1;
  }
}

int find(int a) {
  return a == parent[a] ? a : parent[a] = find(parent[a]);
}

void unite(int a, int b) {
  a = find(a);
  b = find(b);
  if (a != b) {
    if (comp_size[a] < comp_size[b])
      swap(a, b);
    parent[b] = a;
    comp_size[a] += comp_size[b];
  }
}

int main() {
  scanf("%d %d %d", &N, &M, &U);
  for (int i = 0; i < M; i++) {
    scanf("%d %d %d", &edges[i][1], &edges[i][2], &edges[i][0]);
    --edges[i][1];
    --edges[i][2];
  }
  for (int i = 0; i < U; i++) {
    scanf("%d %d %d", &queries[i][1], &queries[i][2], &queries[i][0]);
    --queries[i][1];
    --queries[i][2];
    queries[i][3] = i;
  }
  sort(edges.begin(), edges.begin() + M);
  sort(queries.begin(), queries.begin() + U);
  disjointSets();
  int j = 0;
  for (int i = 0; i < U; i++) {
    while (j < M && edges[j][0] <= queries[i][0]) {
      unite(edges[j][1], edges[j][2]);
      ++j;
    }
    ans[queries[i][3]] = find(queries[i][1]) == find(queries[i][2]) ? "TAIP" : "NE";
  }
  for (int i = 0; i < U; i++) 
    printf("%s\n", ans[i].c_str());
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |   scanf("%d %d %d", &N, &M, &U);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:38:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d %d %d", &edges[i][1], &edges[i][2], &edges[i][0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d %d %d", &queries[i][1], &queries[i][2], &queries[i][0]);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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