oj.uz

Submission #3137

# Submission time Handle Problem Language Result Execution time Memory
3137 2013-08-26T07:40:43 Z club4208 Saveit (IOI10_saveit) C++
100 / 100
 584 ms 15080 KB 
#include<stdio.h>
#include "grader.h"
#include "encoder.h"
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>pii;
void encode(int cit, int hab, int way, int *va, int *vb)
{
  vector<int>pat[1000];
  int dist[36][1000];
  for(int i=0;i<way;i++)
    {
      pat[va[i]].push_back(vb[i]);
      pat[vb[i]].push_back(va[i]);
    }
  for(int i=0;i<hab;i++)
    {
      for(int j=0;j<cit;j++)
	{
	  dist[i][j]=-1;
	}
    }
  for(int p=0;p<hab;p++)
    {
      queue<pii>que;
      que.push(make_pair(0,p));
      for(;;)
	{
	  if(que.empty())
	    {
	      break;
	    }
	  pii zan=que.front();
	  que.pop();
	  if(dist[p][zan.second]!=-1)
	    {
	      continue;
	    }
	  dist[p][zan.second]=zan.first;
	  for(int i=0;i<pat[zan.second].size();i++)
	    {
	      if(dist[p][pat[zan.second][i]]==-1)
		{
		  que.push(make_pair(zan.first+1,pat[zan.second][i]));
		}
	    }
	}
    }
  queue<int>que;
  bool flag[1000];
  int par[1000];
  fill(flag,flag+1000,false);
  fill(par,par+1000,1023);
  que.push(0);
  for(;;)
    {
      if(que.empty())
	{
	  break;
	}
      int zan=que.front();
      que.pop();
      if(flag[zan])
	{
	  continue;
	}
      flag[zan]=true;
      for(int i=0;i<pat[zan].size();i++)
	{
	  if(!flag[pat[zan][i]])
	    {
	      que.push(pat[zan][i]);
	      par[pat[zan][i]]=zan;
	    }
	}
    }
  for(int i=1;i<cit;i++)
    {
      for(int j=9;j>=0;j--)
	{
	  encode_bit((par[i]>>j)&1);
	}
    }
  for(int i=0;i<hab;i++)
    {
      for(int j=9;j>=0;j--)
	{
	  encode_bit((dist[i][0]>>j)&1);
	}
    }
  for(int i=0;i<hab;i++)
    {
      int now=0;
      for(int j=1;j<cit;j++)
	{
	  now*=3;
	  if(dist[i][par[j]]==dist[i][j])
	    {
	      now+=0;
	    }
	  if(dist[i][par[j]]==dist[i][j]+1)
	    {
	      now+=1;
	    }
	  if(dist[i][par[j]]==dist[i][j]-1)
	    {
	      now+=2;
	    }
	  if(j%5==0||j==cit-1)
	    {
	      for(;;)
		{
		  if(j%5!=0)
		    {
		      j++;
		      now*=3;
		    }
		  else
		    {
		      break;
		    }
		}
	      for(int k=7;k>=0;k--)
		{
		  encode_bit((now>>k)&1);
		}
	      now=0;
	    }
	}
    }
}
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include "grader.h"
#include "decoder.h"
using namespace std;
void decode(int cit, int hab)
{
  int par[1000];
  vector<int>ko[1000];
  int st[36];
  par[0]=-1;
  for(int i=1;i<cit;i++)
    {
      int now=0;
      for(int j=0;j<10;j++)
	{
	  now*=2;
	  now+=decode_bit();
	}
      par[i]=now;
      ko[now].push_back(i);
    }
  for(int i=0;i<hab;i++)
    {
      int now=0;
      for(int j=0;j<10;j++)
	{
	  now*=2;
	  now+=decode_bit();
	}
      st[i]=now;
    }
  for(int p=0;p<hab;p++)
    {
      int data[1000];
      data[0]=st[p];
      int cod[1000];
      for(int i=0;i<(cit-1+4)/5;i++)
	{
	  int now=0;
	  for(int j=0;j<8;j++)
	    {
	      now*=2;
	      now+=decode_bit();
	    }
	  for(int j=0;j<5;j++)
	    {
	      if(i*5+1+4-j<cit)
		{
		  cod[i*5+1+4-j]=now%3;
		}
	      now/=3;
	    }
	}
      for(int i=1;i<cit;i++)
	{
	  if(cod[i]==0)
	    {
	      data[i]=0;
	    }
	  if(cod[i]==1)
	    {
	      data[i]=-1;
	    }
	  if(cod[i]==2)
	    {
	      data[i]=1;
	    }
	}
      queue<int>que;
      que.push(0);
      for(;;)
	{
	  if(que.empty())
	    {
	      break;
	    }
	  int zan=que.front();
	  que.pop();
	  if(zan!=0)
	    {
	      data[zan]+=data[par[zan]];
	    }
	  hops(p,zan,data[zan]);
	  for(int i=0;i<ko[zan].size();i++)
	    {
	      que.push(ko[zan][i]);
	    }
	}
    }
}

Compilation message

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<pat[zan.second].size();i++)
                ~^~~~~~~~~~~~~~~~~~~~~~~
encoder.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<pat[zan].size();i++)
                   ~^~~~~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<ko[zan].size();i++)
                ~^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 15080 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4672 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5556 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 9 ms 4688 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 38 ms 5876 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 27 ms 5744 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 71 ms 6156 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5488 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 36 ms 5748 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 33 ms 5656 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 5776 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5512 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 103 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 33 ms 5688 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 37 ms 5752 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 86 ms 6324 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 71 ms 6264 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 90 ms 6440 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 62 ms 6196 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 128 ms 6920 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 162 ms 6928 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 80 ms 6444 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 194 ms 7320 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 15080 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4672 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5556 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 9 ms 4688 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 38 ms 5876 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 27 ms 5744 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 71 ms 6156 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5488 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 36 ms 5748 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 33 ms 5656 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 5776 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5512 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 103 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 33 ms 5688 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 37 ms 5752 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 86 ms 6324 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 71 ms 6264 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 90 ms 6440 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 62 ms 6196 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 128 ms 6920 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 162 ms 6928 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 80 ms 6444 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 194 ms 7320 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 15080 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4672 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5556 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 9 ms 4688 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 38 ms 5876 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 27 ms 5744 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 71 ms 6156 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5488 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 36 ms 5748 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 33 ms 5656 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 5776 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5512 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 103 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 33 ms 5688 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 37 ms 5752 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 86 ms 6324 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 71 ms 6264 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 90 ms 6440 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 62 ms 6196 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 128 ms 6920 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 162 ms 6928 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 80 ms 6444 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 194 ms 7320 KB Output is correct - 67950 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 584 ms 15080 KB Output is correct - 67950 call(s) of encode_bit()
2 Correct 7 ms 4672 KB Output is correct - 94 call(s) of encode_bit()
3 Correct 27 ms 5556 KB Output is correct - 61190 call(s) of encode_bit()
4 Correct 9 ms 4688 KB Output is correct - 130 call(s) of encode_bit()
5 Correct 38 ms 5876 KB Output is correct - 61190 call(s) of encode_bit()
6 Correct 27 ms 5744 KB Output is correct - 67950 call(s) of encode_bit()
7 Correct 71 ms 6156 KB Output is correct - 67950 call(s) of encode_bit()
8 Correct 27 ms 5488 KB Output is correct - 65256 call(s) of encode_bit()
9 Correct 36 ms 5748 KB Output is correct - 67950 call(s) of encode_bit()
10 Correct 33 ms 5656 KB Output is correct - 67950 call(s) of encode_bit()
11 Correct 41 ms 5776 KB Output is correct - 67950 call(s) of encode_bit()
12 Correct 30 ms 5512 KB Output is correct - 67950 call(s) of encode_bit()
13 Correct 103 ms 6524 KB Output is correct - 67950 call(s) of encode_bit()
14 Correct 33 ms 5688 KB Output is correct - 67950 call(s) of encode_bit()
15 Correct 37 ms 5752 KB Output is correct - 67950 call(s) of encode_bit()
16 Correct 86 ms 6324 KB Output is correct - 67950 call(s) of encode_bit()
17 Correct 71 ms 6264 KB Output is correct - 67950 call(s) of encode_bit()
18 Correct 90 ms 6440 KB Output is correct - 67950 call(s) of encode_bit()
19 Correct 62 ms 6196 KB Output is correct - 67950 call(s) of encode_bit()
20 Correct 128 ms 6920 KB Output is correct - 67950 call(s) of encode_bit()
21 Correct 162 ms 6928 KB Output is correct - 67950 call(s) of encode_bit()
22 Correct 80 ms 6444 KB Output is correct - 67950 call(s) of encode_bit()
23 Correct 194 ms 7320 KB Output is correct - 67950 call(s) of encode_bit()