oj.uz

Submission #961713

# Submission time Handle Problem Language Result Execution time Memory
961713 2024-04-12T11:01:04 Z mannshah1211 Sightseeing (NOI14_sightseeing) C++17
25 / 25
 1501 ms 199292 KB 
/**
 *  author: hashman
 *  created: 
**/

#include <bits/stdc++.h>

using namespace std;

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
   if (!first) {
    res += ", ";
   }
   first = false;
   res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() {
  cerr << endl;
}

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);

class edge {
  public:
  int a, b, w;
  bool operator<(const edge& other) const {
    return (w > other.w);
  }
};

class dsu {
  public:
  vector<int> link, siz;
  dsu(int n) : link(n), siz(n, 1) {
    iota(link.begin(), link.end(), 0);
  }
  int who(int u) {
    if (link[u] == u) {
      return u;
    }
    return link[u] = who(link[u]);
  }
  bool unite(int u, int v) {
    u = who(u); v = who(v);
    if (u == v) {
      return false;
    }
    if (siz[u] < siz[v]) {
      swap(u, v);
    }
    siz[u] += siz[v]; link[v] = u;
    return true;
  }
};

const int inf = 1e9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m, q;
  cin >> n >> m >> q;
  vector<edge> edges(m);
  for (int i = 0; i < m; i++) {
    cin >> edges[i].a >> edges[i].b >> edges[i].w;
    edges[i].a--; edges[i].b--;
  }
  sort(edges.begin(), edges.end());
  dsu ds(n);
  vector<vector<pair<int, int>>> g(n);
  for (int i = 0; i < m; i++) {
    if (ds.unite(edges[i].a, edges[i].b)) {
      g[edges[i].a].push_back(make_pair(edges[i].b, edges[i].w));
      g[edges[i].b].push_back(make_pair(edges[i].a, edges[i].w));
    }
  }
  vector<int> ans(n, inf);
  auto dfs = [&](auto&& self, int v, int pr) -> void {
    for (auto [u, w] : g[v]) {
      if (u != pr) {
        ans[u] = min(ans[v], w);
        self(self, u, v);
      }
    }
  };
  dfs(dfs, 0, -1);
  for (int i = 0; i < q; i++) {
    int x;
    cin >> x;
    cout << ans[--x] << '\n';
  }
}

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 348 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 19 ms 4440 KB Output is correct
2 Correct 16 ms 3932 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 966 ms 122004 KB Output is correct
2 Correct 1501 ms 199292 KB Output is correct