oj.uz

Submission #121459

# Submission time Handle Problem Language Result Execution time Memory
121459 2019-06-26T14:20:25 Z TadijaSebez Teleporters (IOI08_teleporters) C++11
100 / 100
 992 ms 56232 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
#define pb push_back
const int N=1000050;
const int M=2*N;
int x[M],my[M];
vector<int> id;
int go[M];
bool comp(int i, int j){ return x[i]<x[j];}
bool was[M];
int sz;
void DFS(int u)
{
	if(was[u]) return;
	was[u]=1;if(u!=1) sz++;
	if(go[u]) DFS(go[u]);
}
int main()
{
	int n,m,i;
	scanf("%i %i",&n,&m);
	for(i=1;i<=n;i++)
	{
		id.pb(i<<1);
		id.pb(i<<1|1);
		scanf("%i %i",&x[i<<1],&x[i<<1|1]);
	}
	sort(id.begin(),id.end(),comp);
	id.pb(1);
	for(i=0;i<id.size();i++) my[id[i]]=i;
	for(i=0;i<id.size()-1;i++)
	{
		int g=id[i]^1;
		int p=my[g];
		go[id[i]]=id[p+1];
	}
	DFS(id[0]);
	int path=sz;
	//printf("path:%i\n",path);
	vector<int> cyc;
	for(i=1;i<id.size()-1;i++)
	{
		if(!was[id[i]]) sz=0,DFS(id[i]),cyc.pb(sz);//,printf("cycle:%i\n",sz);
	}
	int sol=path;
	sort(cyc.rbegin(),cyc.rend());
	int k=0;
	for(i=0;i<m && i<cyc.size();i++)
	{
		sol+=cyc[i]+2;
		k++;
	}
	m-=k;
	int ok=0;
	while(m--)
	{
		if(ok) sol+=3;
		else sol+=1;
		ok^=1;
	}
	printf("%i\n",sol);
	return 0;
}

Compilation message

teleporters.cpp: In function 'int main()':
teleporters.cpp:32:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<id.size();i++) my[id[i]]=i;
          ~^~~~~~~~~~
teleporters.cpp:33:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<id.size()-1;i++)
          ~^~~~~~~~~~~~
teleporters.cpp:43:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1;i<id.size()-1;i++)
          ~^~~~~~~~~~~~
teleporters.cpp:50:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<m && i<cyc.size();i++)
                 ~^~~~~~~~~~~
teleporters.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
teleporters.cpp:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&x[i<<1],&x[i<<1|1]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct

Subtask #6
5.0 / 5.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
5.0 / 5.0

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

Subtask #9
5.0 / 5.0

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

Subtask #10
5.0 / 5.0

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

Subtask #11
5.0 / 5.0

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

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 7 ms 896 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 7 ms 932 KB Output is correct
3 Correct 16 ms 1536 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1012 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1148 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 5428 KB Output is correct
2 Correct 196 ms 11648 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 8668 KB Output is correct
2 Correct 325 ms 16828 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 25540 KB Output is correct
2 Correct 613 ms 30032 KB Output is correct
3 Correct 685 ms 35792 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 33752 KB Output is correct
2 Correct 914 ms 36680 KB Output is correct
3 Correct 876 ms 33944 KB Output is correct
4 Correct 976 ms 34696 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 992 ms 40856 KB Output is correct
2 Correct 988 ms 41228 KB Output is correct
3 Correct 491 ms 56212 KB Output is correct
4 Correct 906 ms 56232 KB Output is correct