Submission #121459

#	Time	Username	Problem	Language	Result	Execution time	Memory
121459		TadijaSebez	Teleporters (IOI08_teleporters)	C++11	100 / 100	992 ms	56232 KiB

teleporters

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=1000050;
const int M=2*N;
int x[M],my[M];
vector<int> id;
int go[M];
bool comp(int i, int j){ return x[i]<x[j];}
bool was[M];
int sz;
void DFS(int u)
{
	if(was[u]) return;
	was[u]=1;if(u!=1) sz++;
	if(go[u]) DFS(go[u]);
}
int main()
{
	int n,m,i;
	scanf("%i %i",&n,&m);
	for(i=1;i<=n;i++)
	{
		id.pb(i<<1);
		id.pb(i<<1|1);
		scanf("%i %i",&x[i<<1],&x[i<<1|1]);
	}
	sort(id.begin(),id.end(),comp);
	id.pb(1);
	for(i=0;i<id.size();i++) my[id[i]]=i;
	for(i=0;i<id.size()-1;i++)
	{
		int g=id[i]^1;
		int p=my[g];
		go[id[i]]=id[p+1];
	}
	DFS(id[0]);
	int path=sz;
	//printf("path:%i\n",path);
	vector<int> cyc;
	for(i=1;i<id.size()-1;i++)
	{
		if(!was[id[i]]) sz=0,DFS(id[i]),cyc.pb(sz);//,printf("cycle:%i\n",sz);
	}
	int sol=path;
	sort(cyc.rbegin(),cyc.rend());
	int k=0;
	for(i=0;i<m && i<cyc.size();i++)
	{
		sol+=cyc[i]+2;
		k++;
	}
	m-=k;
	int ok=0;
	while(m--)
	{
		if(ok) sol+=3;
		else sol+=1;
		ok^=1;
	}
	printf("%i\n",sol);
	return 0;
}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:32:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<id.size();i++) my[id[i]]=i;
          ~^~~~~~~~~~
teleporters.cpp:33:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<id.size()-1;i++)
          ~^~~~~~~~~~~~
teleporters.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1;i<id.size()-1;i++)
          ~^~~~~~~~~~~~
teleporters.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<m && i<cyc.size();i++)
                 ~^~~~~~~~~~~
teleporters.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
teleporters.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x[i<<1],&x[i<<1|1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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