Submission #217534

#	Time	Username	Problem	Language	Result	Execution time	Memory
217534		arnold518	Teleporters (IOI08_teleporters)	C++14	90 / 100	1094 ms	45140 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 par[MAXN+10], sz[MAXN+10];
int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); if(x==y) return; par[x]=y; sz[y]+=sz[x]; }

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());

	for(i=0; i<=2*N; i++) par[i]=i, sz[i]=1;
	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();
		Union(a, b+1);
		Union(a+1, b);
	}

	priority_queue<int> PQ;
	for(i=0; i<=2*N; i++) if(par[i]==i && i!=Find(0)) PQ.push(sz[i]);

	int ans=sz[Find(0)];
	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:19:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
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:22: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: 0 / 5
• Subtask 20: 0 / 5