oj.uz

Submission #53994

# Submission time Handle Problem Language Result Execution time Memory
53994 2018-07-02T07:24:28 Z 윤교준(#1456) Teleporters (IOI08_teleporters) C++11
100 / 100
 898 ms 110816 KB 
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>
#include <queue>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmax(a,b) (a)=max((a),(b))
#define upmin(a,b) (a)=min((a),(b))
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;

int f(vector<int> &V, int i) {
	chk[i] = true;
	V.pb(i);
	i = C[i];
	if (!i) return 0;
	if (chk[i]) return i;
	return f(V, i);
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	ios::sync_with_stdio(false);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> A[i] >> B[i];
	}

	VX.pb(0); VX.pb(MAXX - 1);
	for (int i = 1; i <= N; i++) {
		VX.pb(A[i]);
		VX.pb(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]];
	}

	{
		vector<int> V;
		f(V, 1);
		Ans = sz(V) - 1;
	}

	for (int i = 1; i < sz(VX); i++) {
		if (chk[i]) continue;
		vector<int> V;
		int t = f(V, i);
		if (V[0] != t) {
			puts("SEX");
		}
		PQ.push(sz(V));
	}

	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 492 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

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

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1492 KB Output is correct
2 Correct 8 ms 2004 KB Output is correct
3 Correct 25 ms 4072 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 11240 KB Output is correct
2 Correct 251 ms 27052 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 27052 KB Output is correct
2 Correct 397 ms 41812 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 41812 KB Output is correct
2 Correct 642 ms 43456 KB Output is correct
3 Correct 628 ms 65980 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 823 ms 65980 KB Output is correct
2 Correct 898 ms 65980 KB Output is correct
3 Correct 792 ms 109488 KB Output is correct
4 Correct 825 ms 110816 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 849 ms 110816 KB Output is correct
2 Correct 849 ms 110816 KB Output is correct
3 Correct 559 ms 110816 KB Output is correct
4 Correct 808 ms 110816 KB Output is correct