Submission #910598

#	Time	Username	Problem	Language	Result	Execution time	Memory
910598		josanneo22	Teleporters (IOI08_teleporters)	C++17	85 / 100	414 ms	65536 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)

constexpr int _N = 2E6 + 5;
struct node{
	bool first;
	int index, pos, left, right;
}a[_N];
inline bool cmp(const node &A, const node &B){ return A.pos < B.pos;}
int nxt[_N], N, M, sz[_N], vis[_N], cnt;
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].first = true;
		a[i].index = i;
		a[i].pos = l;
		
		a[i + N].first = false;
		a[i + N].index = i;
		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].first){
			a[i].left = N + a[i].index;
			a[i].right = a[i].index;
		}
		else{
			a[i].left = a[i].index;
			a[i].right = N + a[i].index;
		}
		//cerr << a[i].left << ' ' << a[i].right << ' ';
	}
	//cerr << '\n';
	a[0].right = 0;
	L(i, 1, 2 * N) nxt[a[i - 1].right] = a[i].left;
	nxt[a[2 * N].right] = 0;
	
	function<void(int)> dfs = [&](int u){
		if(vis[u]) return;
		vis[u] = true;
		sz[cnt]++;
		int v = nxt[u];
		if(!vis[v]) dfs(v);
	};
	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: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5