Submission #157088

#	Time	Username	Problem	Language	Result	Execution time	Memory
157088		youngyojun	Teleporters (IOI08_teleporters)	C++11	85 / 100	751 ms	65540 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))
#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;
 
void f(vector<int> &V, int i) {
	chk[i] = true;
	V.eb(i); i = C[i];
	if(!i || chk[i]) return;
	f(V, i);
}
 
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]];
	}
 
	{
		vector<int> V; f(V, 1);
		Ans = sz(V)-1;
	}
 
	for(int i = 1, n = sz(VX); i < n; i++) {
		if(chk[i]) continue;
		vector<int> V;
		f(V, i);
		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 / 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: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5