oj.uz

Submission #262153

# Submission time Handle Problem Language Result Execution time Memory
262153 2020-08-12T12:10:51 Z WLZ Teleporters (IOI08_teleporters) C++14
75 / 100
 1000 ms 65540 KB 
#include <bits/stdc++.h>
using namespace std;

vector< vector<int> > g;
vector<bool> was;
int sz = 0;

void dfs(int u) {
  was[u] = true;
  for (auto& v : g[u]) {
    sz++;
    if (!was[v]) {
      dfs(v);
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  map<int, int> other;
  vector<int> a;
  for (int i = 0; i < n; i++) {
    int w, e;
    cin >> w >> e;
    other[w] = e;
    other[e] = w;
    a.push_back(e);
    a.push_back(w);
  }
  sort(a.begin(), a.end());
  g.resize(2 * n + 1);
  for (int i = 0; i < 2 * n; i++) {
    g[i].push_back(upper_bound(a.begin(), a.end(), other[a[i]]) - a.begin());
  }  
  was.assign(2 * n + 1, false);
  dfs(0);
  int ans = sz;
  priority_queue<int> pq;
  for (int i = 0; i <= 2 * n; i++) {
    if (!was[i]) {
      sz = 0;
      dfs(i);
      pq.push(sz);
    }
  }
  while (m > 0 && !pq.empty()) {
    ans += pq.top() + 2;
    pq.pop();
    m--;
  }
  while (m > 0) {
    ans++;
    m--;
    if (m > 0) {
      ans += 3;
      m--;
    }
  }
  cout << ans + m << '\n';
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1152 KB Output is correct
2 Correct 16 ms 2816 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1664 KB Output is correct
2 Correct 23 ms 3192 KB Output is correct
3 Correct 54 ms 8952 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 3968 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 4604 KB Output is correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 31932 KB Output is correct
2 Runtime error 722 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 521 ms 51560 KB Output is correct
2 Runtime error 938 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1042 ms 61152 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 65536 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 61020 KB Time limit exceeded
2 Halted 0 ms 0 KB -