oj.uz

Submission #341763

# Submission time Handle Problem Language Result Execution time Memory
341763 2020-12-30T23:49:47 Z ogibogi2004 Saveit (IOI10_saveit) C++14
0 / 100
 290 ms 14940 KB 
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
string s;
int dist[40][1024];
vector<int>g[1024];
void bfs(int u)
{
	queue<int>q;
	q.push(u);
	for(int i=0;i<1024;i++)
	{
		dist[u][i]=100000;
	}
	dist[u][u]=0;
	while(!q.empty())
	{
		int u1=q.front();
		q.pop();
		for(auto v:g[u1])
		{
			if(dist[u][u1]+1<dist[u][v])
			{
				dist[u][v]=dist[u][u1]+1;
				q.push(v);
			}
		}
	}
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
  for(int i=0;i<ne;i++)
  {
	  g[v1[i]].push_back(v2[i]);
	  g[v2[i]].push_back(v1[i]);
  }
  for(int i=0;i<nh;i++)
  {
	  bfs(i);
  }
  for(int i=0;i<nh;i++)
  {
	  for(int j=i+1;j<nh;j++)
	  {
		  for(int l=0;l<10;l++)
		  {
			  if((1<<l)&dist[i][j])
			  {
				  s+='1';
			  }
			  else s+='0';
		  }
	  }
  }
  for(int i=nh;i<nv;i++)
  {
	  int smallest=100000;
	  vector<int>v;
	  for(int j=0;j<nh;j++)
	  {
		  if(dist[j][i]<smallest)
		  {
			  smallest=dist[j][i];
			  v.clear();
		  }
		  if(dist[j][i]==smallest)
		  {
			  v.push_back(j);
		  }
	  }
	  bool b[40];
	  memset(b,0,sizeof(b));
	  for(auto xd:v)b[xd]=1;
	  for(int l=0;l<nh;l++)
	  {
		  if(b[l])s+="1";
		  else s+="0";
	  }
	  /*for(int l=0;l<6;l++)
	  {
		  if((1<<l)&p.second)
		  {
			  s+="1";
		  }
		  else s+="0";
	  }*/
	  for(int l=0;l<10;l++)
	  {
		  if((1<<l)&smallest)
		  {
			  s+="1";
		  }
		  else s+="0";
	  }
  }
  for(int i=0;i<s.size();i++)encode_bit((int)s[i]-'0');
  return;
}

#include "grader.h"
#include "decoder.h"
#include<bits/stdc++.h>
using namespace std;
int dist[1024][1024];
int dist_to_closest[1024];
vector<int>closest[1024];
void decode(int nv, int nh) {
	memset(dist,0,sizeof(dist));
	for(int i=0;i<nh;i++)
	{
		for(int j=i+1;j<nh;j++)
		{
			for(int l=0;l<10;l++)
			{
				int x=decode_bit();
				dist[i][j]+=(x<<l);
			}
			dist[j][i]=dist[i][j];
		}
	}
	for(int i=nh;i<nv;i++)
	{
		for(int l=0;l<nh;l++)
		{
			int x=decode_bit();
			if(x==1)closest[i].push_back(l);
		}
		for(int l=0;l<10;l++)
		{
			int x=decode_bit();
			dist_to_closest[i]+=(x<<l);
		}
	}
	for(int i=0;i<nh;i++)
	{
		for(int j=0;j<nh;j++)
		{
			hops(i,j,dist[i][j]);
		}
	}
	/*for(int i=nh;i<nv;i++)
	{
		for(int j=0;j<nh;j++)
		{
			
		}
	}*/
	for(int i=nh;i<nv;i++)
	{
		for(int j=0;j<nh;j++)
		{
			int ans=10000;
			for(auto l:closest[i])
			{
				ans=min(ans,dist[l][j]+dist_to_closest[i]);
			}
			hops(j,i,ans);
		}
	}
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:96:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |   for(int i=0;i<s.size();i++)encode_bit((int)s[i]-'0');
      |               ~^~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 14940 KB Output is correct - 50644 call(s) of encode_bit()
2 Correct 5 ms 8800 KB Output is correct - 56 call(s) of encode_bit()
3 Incorrect 23 ms 9696 KB Output isn't correct
4 Correct 5 ms 8800 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 30 ms 9952 KB Output isn't correct
6 Incorrect 28 ms 9952 KB Output isn't correct
7 Incorrect 48 ms 10208 KB Output isn't correct
8 Incorrect 24 ms 9696 KB Output isn't correct
9 Incorrect 25 ms 9696 KB Output isn't correct
10 Incorrect 25 ms 9696 KB Output isn't correct
11 Incorrect 31 ms 9796 KB Output isn't correct
12 Incorrect 19 ms 9696 KB Output isn't correct
13 Incorrect 57 ms 10380 KB Output isn't correct
14 Incorrect 25 ms 9696 KB Output isn't correct
15 Incorrect 28 ms 9824 KB Output isn't correct
16 Incorrect 59 ms 10208 KB Output isn't correct
17 Incorrect 52 ms 10260 KB Output isn't correct
18 Incorrect 61 ms 10488 KB Output isn't correct
19 Incorrect 41 ms 10080 KB Output isn't correct
20 Incorrect 73 ms 10848 KB Output isn't correct
21 Incorrect 75 ms 11104 KB Output isn't correct
22 Incorrect 56 ms 10464 KB Output isn't correct
23 Incorrect 89 ms 11104 KB Output isn't correct

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 14940 KB Output is correct - 50644 call(s) of encode_bit()
2 Correct 5 ms 8800 KB Output is correct - 56 call(s) of encode_bit()
3 Incorrect 23 ms 9696 KB Output isn't correct
4 Correct 5 ms 8800 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 30 ms 9952 KB Output isn't correct
6 Incorrect 28 ms 9952 KB Output isn't correct
7 Incorrect 48 ms 10208 KB Output isn't correct
8 Incorrect 24 ms 9696 KB Output isn't correct
9 Incorrect 25 ms 9696 KB Output isn't correct
10 Incorrect 25 ms 9696 KB Output isn't correct
11 Incorrect 31 ms 9796 KB Output isn't correct
12 Incorrect 19 ms 9696 KB Output isn't correct
13 Incorrect 57 ms 10380 KB Output isn't correct
14 Incorrect 25 ms 9696 KB Output isn't correct
15 Incorrect 28 ms 9824 KB Output isn't correct
16 Incorrect 59 ms 10208 KB Output isn't correct
17 Incorrect 52 ms 10260 KB Output isn't correct
18 Incorrect 61 ms 10488 KB Output isn't correct
19 Incorrect 41 ms 10080 KB Output isn't correct
20 Incorrect 73 ms 10848 KB Output isn't correct
21 Incorrect 75 ms 11104 KB Output isn't correct
22 Incorrect 56 ms 10464 KB Output isn't correct
23 Incorrect 89 ms 11104 KB Output isn't correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 14940 KB Output is correct - 50644 call(s) of encode_bit()
2 Correct 5 ms 8800 KB Output is correct - 56 call(s) of encode_bit()
3 Incorrect 23 ms 9696 KB Output isn't correct
4 Correct 5 ms 8800 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 30 ms 9952 KB Output isn't correct
6 Incorrect 28 ms 9952 KB Output isn't correct
7 Incorrect 48 ms 10208 KB Output isn't correct
8 Incorrect 24 ms 9696 KB Output isn't correct
9 Incorrect 25 ms 9696 KB Output isn't correct
10 Incorrect 25 ms 9696 KB Output isn't correct
11 Incorrect 31 ms 9796 KB Output isn't correct
12 Incorrect 19 ms 9696 KB Output isn't correct
13 Incorrect 57 ms 10380 KB Output isn't correct
14 Incorrect 25 ms 9696 KB Output isn't correct
15 Incorrect 28 ms 9824 KB Output isn't correct
16 Incorrect 59 ms 10208 KB Output isn't correct
17 Incorrect 52 ms 10260 KB Output isn't correct
18 Incorrect 61 ms 10488 KB Output isn't correct
19 Incorrect 41 ms 10080 KB Output isn't correct
20 Incorrect 73 ms 10848 KB Output isn't correct
21 Incorrect 75 ms 11104 KB Output isn't correct
22 Incorrect 56 ms 10464 KB Output isn't correct
23 Incorrect 89 ms 11104 KB Output isn't correct

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 14940 KB Output is correct - 50644 call(s) of encode_bit()
2 Correct 5 ms 8800 KB Output is correct - 56 call(s) of encode_bit()
3 Incorrect 23 ms 9696 KB Output isn't correct
4 Correct 5 ms 8800 KB Output is correct - 100 call(s) of encode_bit()
5 Incorrect 30 ms 9952 KB Output isn't correct
6 Incorrect 28 ms 9952 KB Output isn't correct
7 Incorrect 48 ms 10208 KB Output isn't correct
8 Incorrect 24 ms 9696 KB Output isn't correct
9 Incorrect 25 ms 9696 KB Output isn't correct
10 Incorrect 25 ms 9696 KB Output isn't correct
11 Incorrect 31 ms 9796 KB Output isn't correct
12 Incorrect 19 ms 9696 KB Output isn't correct
13 Incorrect 57 ms 10380 KB Output isn't correct
14 Incorrect 25 ms 9696 KB Output isn't correct
15 Incorrect 28 ms 9824 KB Output isn't correct
16 Incorrect 59 ms 10208 KB Output isn't correct
17 Incorrect 52 ms 10260 KB Output isn't correct
18 Incorrect 61 ms 10488 KB Output isn't correct
19 Incorrect 41 ms 10080 KB Output isn't correct
20 Incorrect 73 ms 10848 KB Output isn't correct
21 Incorrect 75 ms 11104 KB Output isn't correct
22 Incorrect 56 ms 10464 KB Output isn't correct
23 Incorrect 89 ms 11104 KB Output isn't correct