Submission #157089

#	Time	Username	Problem	Language	Result	Execution time	Memory
157089		youngyojun	Teleporters (IOI08_teleporters)	C++11	100 / 100	682 ms	62408 KiB

teleporters

#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 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5