Submission #910633

#	Time	Username	Problem	Language	Result	Execution time	Memory
910633		josanneo22	Teleporters (IOI08_teleporters)	C++17	100 / 100	403 ms	48076 KiB

teleporters

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

#define L(i,j,k) for(int i=(j);i<=(k);++i)
#define R(i,j,k) for(int i=(j);i>=(k);--i)

struct node {
	int index, pos;
}a[2000005];
inline bool cmp(const node& A, const node& B) { return A.pos < B.pos; }
int nxt[2000005], N, M, sz[2000005], cnt;
bool vis[2000005];
void dfs(int u){
    if (vis[u]) return;
    vis[u] = true;
    sz[cnt]++;
    if (!vis[nxt[u]]) dfs(nxt[u]);
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N >> M;
	L(i, 1, N) {
		int l, r; cin >> l >> r;
		a[i].index = i;
		a[i].pos = l;

		a[i + N].index = i + N;
		a[i + N].pos = r;
	}
	sort(a + 1, a + 2 * N + 1, cmp);
	L(i, 1, N * 2) {
		//cerr << a[i].index << ' ';
		if (a[i].index >= N + 1) {
			int x = a[i].index - N, y = a[i].index;
			a[i].index = y;
			a[i].pos = x;
		}
		else {
			int x = a[i].index, y = N + a[i].index;
			a[i].index = x;
			a[i].pos = y;
		}
		//cerr << a[i].left << ' ' << a[i].right << ' ';
	}
	//cerr << '\n';
	a[0].pos = 0;
	L(i, 1, 2 * N) nxt[a[i - 1].pos] = a[i].index;
	nxt[a[2 * N].pos] = 0;
	
	memset(vis, 0, sizeof(vis));
	memset(sz, 0, sizeof(sz));
	L(i, 0, 2 * N) {
		if (!vis[i]) {
			cnt++;
			sz[cnt] = 0;
			dfs(i);
		}
	}
	//~ L(i, 0, 2 * N){
		//~ cerr << i << " has neighbours : ";
		//~ for(auto & v : G[i]) cerr << v << ' ';
		//~ cerr << '\n';
	//~ }
	sort(sz + 2, sz + cnt + 1, greater<int>());
	int ans = sz[1] - 1;
	//~ cerr << "cycle: ";
	//~ for(auto & v: sz){
		//~ cerr << v << ' ';
	//~ }
	//~ cerr << '\n';
	L(i, 2, cnt) {
		if (M == 0) break;
		M--;
		ans += sz[i];
		ans += 2;
	}
	if (M & 1) { ans++; M--; }
	ans += 2 * M;
	cout << ans << '\n';
}

• 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