Submission #217537

#	Time	Username	Problem	Language	Result	Execution time	Memory
217537		arnold518	Teleporters (IOI08_teleporters)	C++14	95 / 100	1033 ms	42804 KiB

teleporters

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e6;

int N, M;
pii A[MAXN+10];

int adj[MAXN+10];
bool vis[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);

	vector<int> comp;
	for(i=1; i<=N; i++) comp.push_back(A[i].first), comp.push_back(A[i].second);
	sort(comp.begin(), comp.end());

	memset(adj, -1, sizeof(adj));
	for(i=1; i<=N; i++)
	{
		int a=lower_bound(comp.begin(), comp.end(), A[i].first)-comp.begin(), b=lower_bound(comp.begin(), comp.end(), A[i].second)-comp.begin();
		adj[a]=b+1;
		adj[b]=a+1;
	}

	priority_queue<int> PQ;
	int now=0, sz=0;
	while(now!=-1)
	{
		sz++;
		vis[now]=true;
		now=adj[now];
	}
	int ans=sz;

	for(i=0; i<=2*N; i++)
	{
		if(vis[i]) continue;
		now=i; sz=0;
		while(!vis[now])
		{
			sz++;
			vis[now]=true;
			now=adj[now];
		}
		PQ.push(sz);
	}

	while(M--)
	{
		if(!PQ.empty()) ans+=PQ.top()+2, PQ.pop();
		else ans++, PQ.push(1);
	}
	printf("%d\n", ans-1);
}

Compilation message (stderr)

teleporters.cpp: In function 'int main()':
teleporters.cpp:18:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
teleporters.cpp:20: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:21:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d%d", &A[i].first, &A[i].second);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 0 / 5