Submission #1259785

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259785		mdobric	Teleporters (IOI08_teleporters)	C++20	15 / 100	589 ms	117956 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> sus[maxn * 2], ciklusi, v;

int dfs (int x){
	for (int i = 0; i < sus[x].size(); i++){
		if (bio[sus[x][i]] == -1){
			bio[sus[x][i]] = bio[x] + 1;
			return dfs(sus[x][i]);
		}
	}
	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]].push_back(b[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: 0 / 5
• Subtask 3: 5 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 5 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5