Submission #53983

#	Time	Username	Problem	Language	Result	Execution time	Memory
53983		khsoo01	Teleporters (IOI08_teleporters)	C++11	90 / 100	1062 ms	63356 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> cpr, cs;

int cmpr (int V) {
	return lower_bound(cpr.begin(), cpr.end(), V) - cpr.begin();
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&a[i].X,&a[i].Y);
		cpr.push_back(a[i].X);
		cpr.push_back(a[i].Y);
	}
	sort(cpr.begin(), cpr.end());
	for(int i=1;i<=n;i++) {
		a[i].X = cmpr(a[i].X);
		a[i].Y = cmpr(a[i].Y);
		d[a[i].X] = a[i].Y+1;
		d[a[i].Y] = a[i].X+1;
	}
	for(int i=0;!vis[i];i=d[i]) {
		ans++;
		vis[i] = true;
	}
	for(int i=0;i<cpr.size();i++) {
		if(vis[i]) continue;
		int C = 0;
		for(int j=i;!vis[j];j=d[j]) {
			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:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<cpr.size();i++) {
              ~^~~~~~~~~~~
teleporters.cpp:21: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: 0 / 5
• Subtask 20: 0 / 5