Submission #652828

#	Time	Username	Problem	Language	Result	Execution time	Memory
652828		omkarbajaj073	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	3214 ms	125816 KiB

sightseeing

#include <bits/stdc++.h>

#define f first
#define s second
#define mp make_pair
#define piii pair<int, pair<int, int>>

using namespace std;

const int MAX_N = 5e5 + 10;



int n, m, q;
// vector<pair<int, int> > graph[MAX_N];
vector<piii> edges;
map<int, vector<int>> comps;
int par[MAX_N], dist[MAX_N];

int get(int a) {
  if (a != par[a]) par[a] = get(par[a]);
  return par[a];
}

void merge(int a, int b) {
  int x = get(a), y = get(b);
  if (x == y) return;
  if (comps[x].size() < comps[y].size()) swap(x, y);
  par[y] = x;
  while (!comps[y].empty()) {
    int tmp = comps[y].back();
    comps[y].pop_back(); comps[x].push_back(tmp);
  }
}



signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);

  cin >> n >> m >> q;

  for (int i = 0; i < m; i++) {
    int a, b, w; cin >> a >> b >> w;
    if (a > b) swap(a, b);
    // graph[a].push_back({b, w});
    // graph[b].push_back({a, w});
    edges.push_back(mp(w, mp(a, b)));
  }

  sort(edges.begin(), edges.end(), [](const piii& a, const piii& b) {
    if (a.f == b.f) return a.s.f > b.s.f;
    return a.f > b.f;
  });

  for (int i = 2; i <= n; i++) {
    dist[i] = -1;
    par[i] = i; comps[i].push_back(i);
  }
  dist[1] = INT_MAX;
  par[1] = 1;

  for (piii edge: edges) {
    int w = edge.f, a = edge.s.f, b = edge.s.s;
    merge(a, b);
    int x = get(1);
    if (get(a) == x) {
      
      while (!comps[x].empty()) {
        int tmp = comps[x].back();
        comps[x].pop_back();
        dist[tmp] = max(w, dist[tmp]);
      }
      // while (!comps[b].empty()) {
      //   int tmp = comps[b].back();
      //   comps[b].pop_back();
      //   dist[tmp] = max(w, dist[tmp]);
      // }
      // swap(a, b);
      // while (!comps[b].empty()) {
      //   int tmp = comps[b].back();
      //   comps[b].pop_back();
      //   dist[tmp] = max(w, dist[tmp]);
      // }
      continue;
    }
  }

  while (q--) {
    int query; cin >> query;
    cout << dist[query] << endl;
  }

  return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10