oj.uz

Submission #95139

# Submission time Handle Problem Language Result Execution time Memory
95139 2019-01-27T15:01:59 Z Retro3014 Teleporters (IOI08_teleporters) C++17
100 / 100
 532 ms 29156 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <stdio.h>

#define MAX_X 2000000
using namespace std;
typedef long long ll;
int N, M;
int r[MAX_X+1];
bool vst[MAX_X+1];

vector<int> cycle;
int ans;

void dfs(int x, ll y){
	while(1){
		if(vst[x]){
			cycle.push_back(y);
			return;
		}
		vst[x] = true;
		if(x==MAX_X){
			ans+=y;
			return;
		}
		if(r[x]!=x+1)	y++;
		x = r[x];
	}
}

int main(){
	scanf("%d%d", &N, &M);
	for(int i=0; i<MAX_X; i++)	r[i] = i+1;
	for(int i=0; i<N; i++){
		int a, b; scanf("%d%d", &a, &b);
		r[a-1] = b; r[b-1] = a;
	}
	for(int i=0; i<MAX_X; i++){
		if(vst[i])	continue;
		dfs(i, 0);
	}
	sort(cycle.begin(), cycle.end());
	while(M--){
		if(cycle.empty()){
			cycle.push_back(1);
			ans++;
		}else{
			ans+=2+cycle.back();
			cycle.pop_back();
		}
	}
	printf("%d", ans);
	return 0;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:33: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:36:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
             ~~~~~^~~~~~~~~~~~~~~~

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 17 ms 10104 KB Output is correct

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 10088 KB Output is correct
2 Correct 20 ms 10232 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10076 KB Output is correct
2 Correct 21 ms 10280 KB Output is correct
3 Correct 25 ms 10204 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10232 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10204 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10616 KB Output is correct
2 Correct 157 ms 10860 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 10828 KB Output is correct
2 Correct 241 ms 10860 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 12412 KB Output is correct
2 Correct 348 ms 12524 KB Output is correct
3 Correct 338 ms 20836 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 12492 KB Output is correct
2 Correct 444 ms 12524 KB Output is correct
3 Correct 361 ms 24608 KB Output is correct
4 Correct 361 ms 24968 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 414 ms 14584 KB Output is correct
2 Correct 532 ms 29032 KB Output is correct
3 Correct 233 ms 28924 KB Output is correct
4 Correct 408 ms 29156 KB Output is correct