Submission #1006302

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006302		MilosMilutinovic	Sightseeing (NOI14_sightseeing)	C++14	25 / 25	1529 ms	199824 KiB

sightseeing

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10