oj.uz

Submission #53985

# Submission time Handle Problem Language Result Execution time Memory
53985 2018-07-02T07:04:22 Z khsoo01 Teleporters (IOI08_teleporters) C++11
100 / 100
 559 ms 26660 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> cs;

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<N;i++) {
		d[i] = i+1;
	}
	d[N-1] = 0;
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&a[i].X,&a[i].Y);
		d[a[i].X-1] = a[i].Y;
		d[a[i].Y-1] = a[i].X;
	}
	for(int i=0;!vis[i];i=d[i]) {
		if(d[i] != i+1) ans++;
		vis[i] = true;
	}
	for(int i=0;i<N;i++) {
		if(vis[i]) continue;
		int C = 0;
		for(int j=i;!vis[j];j=d[j]) {
			if(d[j] != j+1) 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:17: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 18 ms 10104 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10220 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 10220 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10320 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10320 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10376 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10376 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10376 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10376 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10376 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10376 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10376 KB Output is correct
2 Correct 21 ms 10452 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 10452 KB Output is correct
2 Correct 25 ms 10452 KB Output is correct
3 Correct 32 ms 10596 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 10596 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 10596 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11664 KB Output is correct
2 Correct 199 ms 13384 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 13384 KB Output is correct
2 Correct 287 ms 14440 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 17504 KB Output is correct
2 Correct 397 ms 18524 KB Output is correct
3 Correct 375 ms 20952 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 457 ms 20952 KB Output is correct
2 Correct 547 ms 20952 KB Output is correct
3 Correct 498 ms 22308 KB Output is correct
4 Correct 422 ms 22352 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 26612 KB Output is correct
2 Correct 559 ms 26660 KB Output is correct
3 Correct 298 ms 26660 KB Output is correct
4 Correct 445 ms 26660 KB Output is correct