oj.uz

Submission #51339

# Submission time Handle Problem Language Result Execution time Memory
51339 2018-06-17T13:53:13 Z KieranHorgan Sightseeing (NOI14_sightseeing) C++17
25 / 25
 2932 ms 209604 KB 
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define ll long long
#define int long long
#define ld long double
#define pii pair<int,int>
#define rand() abs((rand()<<15)|rand())
#define randll() abs(((long long)rand()<<30)|rand())

int N, E, Q;

/*-----------------------UNION FIND-----------------------*/
struct UnionFind {
  vector<int> sz, parent;
  int noOfComponents;
  UnionFind(int N_) {
    noOfComponents = N_;
    sz.assign(N_, 1);
    parent.assign(N_, 0);
    for(int i = 0; i < N_; i++) parent[i] = i;
  }
  int findSet(int i) {                            // O(α(N))
    if(i != parent[i])
      return parent[i]=findSet(parent[i]);
    return parent[i];
  }
  int isSameSet(int i,int j){return findSet(i)==findSet(j);}
  void mergeSet(int i, int j) {                   // O(α(N))
    int x = findSet(i);
    int y = findSet(j);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    parent[y] = x;
    sz[x] += sz[y];
    noOfComponents++;
  }
};

/*-----------------MINIMUM SPANNING TREE------------------*/
#define iii pair<int, pair<int, int>>
vector<iii> mst;
vector<iii> EdgeList;
vector<pair<int, int>> AdjList[500005];
void Kruskal() {
  UnionFind UF(N+1);
  sort(EdgeList.rbegin(), EdgeList.rend());        // O(NlogN)
  for(auto e: EdgeList) {                            // O(N)
    int u = e.second.first;
    int v = e.second.second;
    int w = e.first;
    if(!UF.isSameSet(u,v)) {
      UF.mergeSet(u,v);
      AdjList[u].push_back({w, v});
      AdjList[v].push_back({w, u});
    }
  }
}

int ans[500005];
int vis[500005];
void dfs(int u, int d) {
  vis[u] = 1;
  ans[u] = d;
  for(auto v: AdjList[u])
    if(!vis[v.second])
      dfs(v.second, min(d, v.first));
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long seed;
  asm("rdtsc" : "=A"(seed));
  srand(seed);

  cin >> N >> E >> Q;
  for(int i = 0; i < E; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    EdgeList.push_back({w, {u, v}});
  }
  Kruskal();
  dfs(1, 1ll<<29);

  for(int i = 0; i < Q; i++) {
    int x;
    cin >> x;
    cout << ans[x] << endl;
  }
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12152 KB Output is correct
2 Correct 14 ms 12268 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 12308 KB Output is correct
2 Correct 12 ms 12308 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 16336 KB Output is correct
2 Correct 40 ms 16336 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2071 ms 114792 KB Output is correct
2 Correct 2932 ms 209604 KB Output is correct