oj.uz

Submission #53983

# Submission time Handle Problem Language Result Execution time Memory
53983 2018-07-02T06:59:36 Z khsoo01 Teleporters (IOI08_teleporters) C++11
90 / 100
 1000 ms 63356 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 360 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 400 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 456 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 536 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 540 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 672 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 672 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 792 KB Output is correct
2 Correct 10 ms 1080 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1080 KB Output is correct
2 Correct 10 ms 1268 KB Output is correct
3 Correct 27 ms 2080 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2080 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2080 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 4940 KB Output is correct
2 Correct 308 ms 14296 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 14296 KB Output is correct
2 Correct 557 ms 17940 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 25228 KB Output is correct
2 Correct 738 ms 28864 KB Output is correct
3 Correct 806 ms 45696 KB Output is correct

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 909 ms 45696 KB Output is correct
2 Execution timed out 1039 ms 59324 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1062 ms 63356 KB Time limit exceeded
2 Halted 0 ms 0 KB -