oj.uz

Submission #640958

# Submission time Handle Problem Language Result Execution time Memory
640958 2022-09-15T15:24:48 Z christinelynn Cities (BOI16_cities) C++17
22 / 100
 140 ms 4440 KB 
#include <bits/stdc++.h>
using namespace std;

#define nyahalo ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define otsumiko exit(0);
#define mikodanye priority_queue<pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > >
#define mikochi priority_queue<long long, vector<long long>, greater<long long> >

long long n, k, m, u, v, c, tl[6], tp[100069], pw[22], pr[100069], ci, ctu, ans = 1e17, cst;
pair<long long, pair<long long, long long> > ed[100069];
set<long long> st;

long long fd(long long x) {
  if (pr[x] != x) {
    pr[x] = fd(pr[x]);
  }
  return pr[x];
}

int main() {
  nyahalo
  long long i, j, ii;
  pw[0] = 1;
  for (i=1; i<=21; i++) {
    pw[i] = pw[i-1]*2;
  }
  cin >> n >> k >> m;
  for (i=1; i<=n; i++) {
    tp[i] = 0;
    pr[i] = i;
  }
  for (i=1; i<=k; i++) {
    cin >> tl[i];
    tp[tl[i]] = 1;
  }
  for (i=1; i<=m; i++) {
    cin >> ed[i].second.first >> ed[i].second.second >> ed[i].first;
  }
  sort(ed+1, ed+m+1);
  if (n<=20 && m<=40) {
    for (i=0; i<=pw[n]-1; i++) {
      ctu = 0;
      for (j=1; j<=k; j++) {
        ci = tl[j];
        if ((i&pw[ci-1]) == 0) {
          ctu = 1;
          break;
        }
      }
      if (ctu == 1) {
        continue;
      }
      for (j=1; j<=n; j++) {
        pr[j] = j;
      }
      cst = 0;
      for (j=1; j<=m; j++) {
        c = ed[j].first;
        u = ed[j].second.first;
        v = ed[j].second.second;
        if ((i&pw[u-1]) == 0 || (i&pw[v-1]) == 0) {
          continue;
        }
        if (fd(u) != fd(v)) {
          cst += c;
          pr[fd(u)] = fd(v);
        }
      }
      for (j=1; j<=n; j++) {
        if ((i&pw[j-1]) == 0) {
          continue;
        }
        st.insert(fd(j));
      }
      if (st.size()>1) {
        cst = 1e17;
      }
      st.clear();
      ans = min(ans, cst);
    }
    cout << ans << "\n";
    otsumiko
  }
  cout << "sek\n";
  otsumiko
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:22:19: warning: unused variable 'ii' [-Wunused-variable]
   22 |   long long i, j, ii;
      |                   ^~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 140 ms 212 KB Output is correct
3 Correct 76 ms 332 KB Output is correct
4 Correct 37 ms 212 KB Output is correct
5 Correct 24 ms 340 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 4440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 4388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 4376 KB Output isn't correct
2 Halted 0 ms 0 KB -