Submission #53985

#	Time	Username	Problem	Language	Result	Execution time	Memory
53985		khsoo01	Teleporters (IOI08_teleporters)	C++11	100 / 100	559 ms	26660 KiB

teleporters

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 2000005;

int n, m, d[N], ans;
bool vis[N];
pii a[N];

vector<int> cs;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<N;i++) {
		d[i] = i+1;
	}
	d[N-1] = 0;
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&a[i].X,&a[i].Y);
		d[a[i].X-1] = a[i].Y;
		d[a[i].Y-1] = a[i].X;
	}
	for(int i=0;!vis[i];i=d[i]) {
		if(d[i] != i+1) ans++;
		vis[i] = true;
	}
	for(int i=0;i<N;i++) {
		if(vis[i]) continue;
		int C = 0;
		for(int j=i;!vis[j];j=d[j]) {
			if(d[j] != j+1) C++;
			vis[j] = true;
		}
		cs.push_back(C);
	}
	sort(cs.begin(), cs.end());
	for(int i=cs.size();i--;) {
		if(!m) break;
		m--;
		ans += cs[i] + 2;
	}
	for(int i=0;i<m;i++) {
		ans += i%2*2 + 1;
	}
	printf("%d\n", ans-1);
}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
teleporters.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a[i].X,&a[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• 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