Submission #1259811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259811		mdobric	Teleporters (IOI08_teleporters)	C++20	100 / 100	293 ms	47476 KiB

teleporters

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

const int maxn = 1000005;
int n, m, a[maxn], b[maxn], novi[maxn * 2];
int ans, bio[maxn * 2];
vector <int> ciklusi, v;
int sus[maxn * 2];

int dfs (int x){
	if (bio[sus[x]] == -1){
		bio[sus[x]] = bio[x] + 1;
		return dfs(sus[x]);
	}
	return bio[x];
}

int main (void){
	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> n >> m;
	for (int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
		v.push_back(a[i]);
		v.push_back(b[i]);
	}
	sort(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++){
		novi[v[i]] = i;
	}
	for (int i = 0; i < n; i++){
		a[i] = novi[a[i]];
		b[i] = novi[b[i]];
		sus[a[i]] = b[i] + 1;
		sus[b[i]] = a[i] + 1;
	}
	memset(bio, -1, sizeof bio);
	for (int i = 0; i < 2 * n; i++){
		if (bio[i] == -1){
			bio[i] = 0;
			int len = dfs(i);
			//cout << i << "   " << len << endl;
			if (i == 0) ans = len;
			else ciklusi.push_back(len + 1);
		}
	}
	sort(ciklusi.begin(), ciklusi.end());
	reverse(ciklusi.begin(), ciklusi.end());
	int br = 0;
	while (m > 0 and br < ciklusi.size()){
		ans += ciklusi[br] + 2;
		br++;
		m--;
	}
	ans += (m / 2) * 4;
	if (m % 2 == 1) ans++;
	cout << ans << "\n";
	
	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