oj.uz

Submission #121456

# Submission time Handle Problem Language Result Execution time Memory
121456 2019-06-26T14:18:58 Z TadijaSebez Teleporters (IOI08_teleporters) C++11
90 / 100
 1000 ms 40260 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 2 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 1 ms 384 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 4 ms 512 KB Output is correct
2 Correct 7 ms 768 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 8 ms 896 KB Output is correct
3 Correct 16 ms 1404 KB Output is correct

Subtask #14
5.0 / 5.0

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

Subtask #15
5.0 / 5.0

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

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 5072 KB Output is correct
2 Correct 208 ms 11428 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 8288 KB Output is correct
2 Correct 351 ms 16220 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 454 ms 24912 KB Output is correct
2 Correct 588 ms 29384 KB Output is correct
3 Correct 737 ms 34996 KB Output is correct

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 835 ms 33172 KB Output is correct
2 Correct 959 ms 35936 KB Output is correct
3 Execution timed out 1070 ms 33392 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #20
0 / 5.0

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