oj.uz

Submission #157089

# Submission time Handle Problem Language Result Execution time Memory
157089 2019-10-09T12:49:55 Z youngyojun Teleporters (IOI08_teleporters) C++11
100 / 100
 682 ms 62408 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
using namespace std;
typedef long long ll;
 
const int MAXN = 1000005;
const int MAXX = 2000005;
 
priority_queue<int> PQ;
 
vector<int> VX;
 
int C[MAXX];
int LI[MAXX], RI[MAXX];
 
int A[MAXN], B[MAXN];
bitset<MAXX> chk;
 
int N, M, Ans;
 
void f(int i, int &c) {
	chk[i] = true;
	c++; i = C[i];
	if(!i || chk[i]) return;
	f(i, c);
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> M;
	for(int i = 1; i <= N; i++)
		cin >> A[i] >> B[i];
 
	VX.eb(0); VX.eb(MAXX-1);
	for(int i = 1; i <= N; i++) {
		VX.eb(A[i]); VX.eb(B[i]);
	}
	sorv(VX);
 
	LI[0] = 0; RI[MAXX-1] = sz(VX)-1;
	for(int i = 1; i + 1 < sz(VX); i++) {
		RI[VX[i]] = i;
		LI[VX[i]] = i+1;
	}
 
	for(int i = 1; i <= N; i++) {
		C[RI[A[i]]] = LI[B[i]];
		C[RI[B[i]]] = LI[A[i]];
	}
 
 	Ans = -1;
 	for(int i = 1;;) {
 		chk[i] = true; Ans++;
 		i = C[i];
 		if(!i || chk[i]) break;
	}
	for(int i = 1, n = sz(VX), c; i < n; i++) {
		if(chk[i]) continue;
		c = 0; for(int j = i;;) {
			c++; chk[j] = true;
			j = C[j];
			if(!j || chk[j]) break;
		}
		PQ.push(c);
	}
 
	for(; M--;) {
		if(!PQ.empty()) {
			Ans += PQ.top() + 2;
			PQ.pop();
		}
		else {
			Ans++;
			PQ.push(1);
		}
	}
 
	cout << Ans << endl;
	return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 7 ms 1144 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 8 ms 1628 KB Output is correct
3 Correct 15 ms 1656 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 7744 KB Output is correct
2 Correct 188 ms 21388 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 15916 KB Output is correct
2 Correct 296 ms 27732 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 34644 KB Output is correct
2 Correct 469 ms 38100 KB Output is correct
3 Correct 548 ms 51796 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 42656 KB Output is correct
2 Correct 650 ms 46040 KB Output is correct
3 Correct 616 ms 53976 KB Output is correct
4 Correct 625 ms 54440 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 60980 KB Output is correct
2 Correct 682 ms 61160 KB Output is correct
3 Correct 460 ms 62340 KB Output is correct
4 Correct 620 ms 62408 KB Output is correct