oj.uz

Submission #1006302

# Submission time Handle Problem Language Result Execution time Memory
1006302 2024-06-23T17:16:44 Z MilosMilutinovic Sightseeing (NOI14_sightseeing) C++14
25 / 25
 1529 ms 199824 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<array<int, 3>> e;
  for (int i = 0; i < m; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x; --y;
    e.push_back({z, x, y});
  }
  sort(e.rbegin(), e.rend());
  vector<vector<int>> qs(n);
  for (int i = 0; i < q; i++) {
    int x;
    cin >> x;
    --x;
    qs[x].push_back(i);
  }  
  vector<bool> good(n);
  good[0] = true;
  vector<int> root(n);
  iota(root.begin(), root.end(), 0);
  vector<int> res(q, -1);
  function<int(int)> GetRoot = [&](int x) {
    return root[x] == x ? x : root[x] = GetRoot(root[x]);
  };
  auto Unite = [&](int x, int y, int z) {
    x = GetRoot(x);
    y = GetRoot(y);
    if (x == y) {
      return;
    }
    if (qs[x].size() < qs[y].size()) {
      swap(x, y);
    }
    good[x] = (good[x] | good[y]);
    for (int i : qs[y]) {
      qs[x].push_back(i);
    }
    qs[y].clear();
    if (good[x]) {
      for (int i : qs[x]) {
        res[i] = z;
      }
      qs[x].clear();
    }
    root[y] = x;
  };
  for (auto& p : e) {
    Unite(p[1], p[2], p[0]);
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 3028 KB Output is correct
2 Correct 14 ms 2772 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1036 ms 118176 KB Output is correct
2 Correct 1529 ms 199824 KB Output is correct