oj.uz

Submission #229483

# Submission time Handle Problem Language Result Execution time Memory
229483 2020-05-04T15:30:14 Z apostoldaniel854 Teleporters (IOI08_teleporters) C++14
100 / 100
 413 ms 29036 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e6;

int nxt[1 + N + 1];
bool used[1 + N + 1];
typedef long long ll;

int main(){
    ios::sync_with_stdio (false);
    cin.tie (0); cout.tie (0);
	for (int i = 1; i <= N; i++)
		nxt[i] = i + 1;
	used[N + 1] = true;
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		int x, y;
		cin >> x >> y;
		nxt[x] = y + 1;
		nxt[y] = x + 1;
	}
	int ans = -1;
	priority_queue <int> pq;
	for (int i = 1; i <= N; i++) {
		if (used[i] == false) {
            int cur = i, cnt = 0;
			while (used[cur] == false) {
				used[cur] = true;
				if (nxt[cur] != cur + 1)
                    cnt++;
				cur = nxt[cur];
			}
			if (ans == -1)
                ans = cnt;
			else
                pq.push (cnt);
		}
	}
	while (pq.size () && m){
		ans += pq.top () + 2;
		pq.pop ();
		m--;
	}
	ans += (m + 1) / 2;
	ans += (m / 2) * 3;
	cout << ans << "\n";
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10240 KB Output is correct
2 Correct 20 ms 10368 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10240 KB Output is correct
2 Correct 21 ms 10368 KB Output is correct
3 Correct 23 ms 10368 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 10616 KB Output is correct
2 Correct 121 ms 10744 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 10744 KB Output is correct
2 Correct 187 ms 10776 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 12400 KB Output is correct
2 Correct 277 ms 12400 KB Output is correct
3 Correct 311 ms 14316 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 12400 KB Output is correct
2 Correct 362 ms 12304 KB Output is correct
3 Correct 331 ms 24584 KB Output is correct
4 Correct 350 ms 24696 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 14444 KB Output is correct
2 Correct 413 ms 29036 KB Output is correct
3 Correct 317 ms 28904 KB Output is correct
4 Correct 375 ms 29036 KB Output is correct