oj.uz

Submission #380395

# Submission time Handle Problem Language Result Execution time Memory
380395 2021-03-21T12:02:56 Z CaroLinda Saveit (IOI10_saveit) C++14
100 / 100
 1363 ms 19704 KB 
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i = a; i < b ; i++ )
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define pii pair<int,int>

const int MAXN = 1010 ;
const int BASE = 2 ;

using namespace std ;

struct bignum
{
	vector<int> a ;
  
	void trim() 
	{
		while( sz(a) > 0 && a.back() == 0 ) a.pop_back() ;
	}
 
	bignum operator + (bignum other) const
	{
		bignum aux ;
 
		for(int i = 0 , carry = 0 ; i < max(sz(other.a), sz(a)) || carry ; i++ )
		{
			int addOther = (i >= sz(other.a) ) ? 0 : other.a[i] ;
			int addThis = (i >= sz(a) ) ? 0 : a[i] ;
 
			aux.a.push_back( addOther + addThis + carry ) ;
 
			carry = ( aux.a.back() >= BASE ) ;
 
			if(carry) aux.a.back() -= BASE ;
 
		}
 
		return aux ;
 
	}
 
	bool operator < ( bignum other ) const 
	{
		if( sz(a) != sz(other.a) ) return sz(a) < sz(other.a) ;
 
		for(int i = sz(a) - 1 ; i >= 0 ; i-- )
			if( a[i] != other.a[i] ) return a[i] < other.a[i] ;
 
	 	return false ;
	}
 
	bool operator == (bignum other) const  
	{
		return !(*this < other) && !(other < *this) ;
	}
 
	bool operator <= (bignum other) { return !(other < *this ) ; }
 
	bignum operator - (bignum other )const 
	{
		bignum aux ;
 
		for(int i = 0 ,carry=0 ; i < max(sz(a), sz(other.a) )  ; i++ )
		{
 
			int myNumber = ( i >= sz(a) ) ? 0 : a[i] ;
			int otherNumber = ( i >= sz(other.a) ) ? 0 : other.a[i] ;
 
			aux.a.push_back( myNumber - otherNumber - carry ) ;
 
			carry = ( aux.a.back() < 0 ) ;
 
			if(carry ) aux.a.back() += BASE ;
 
		}
 
		aux.trim() ;
		return aux ;
 
	}
 
} ;

static bignum pot[1000] ;

static int N , H ;
static int dist[MAXN] , par[MAXN] ;
static vector<int> adj[MAXN] ;
static vector<int> tree[MAXN] ;
static bool vis[MAXN] ;

bool isOn(int i , int mask ) { return ((1<<i)&mask) != 0 ; }

void dfs(int x)
{
	vis[x] = true ;

	for(auto e : adj[x] )
	{
		if( vis[e] ) continue ;

		tree[x].pb(e) ;
		tree[e].pb(x) ;

		par[e] = x ;

		dfs(e) ;
	}
}

void runBfs(int sc)
{
	vector<int> fila(1,sc) ;
	for(int i = 0 ; i < N ; i++ ) dist[i] = N+10 ;
	dist[sc] = 0 ;

	int ptr = 0 ;
	while(ptr < sz(fila) )
	{
		int x = fila[ptr++] ;

		for(auto e : adj[x] )
		{
			if( dist[e] <= dist[x] + 1 ) continue ;
			dist[e] = dist[x]+1 ;
			fila.pb(e) ;
		}
	}
}

void encode(int nv, int nh, int ne, int *v1, int *v2)
{
	N = nv ;
	H = nh ;

	for(int i = 0 ; i < ne ; i++ )
	{
		adj[ v1[i] ].pb( v2[i] ) ;
		adj[ v2[i] ].pb( v1[i] ) ;
	}	

	dfs(0) ;

	set<int> fila ;
	vector<int> deg(nv+10) ;

	for(int i = 0 ; i < nv ; i++ ) 
	{
		deg[i] = sz(tree[i] ) ;

		if( deg[i] == 1 ) fila.insert(i) ;
	}

	int cnt = nv-2 ;

	while( cnt-- )
	{
		int x = *fila.begin() ;
		deg[x] = 0 ;
		fila.erase( fila.begin() ) ;

		for(auto e : tree[x] )
			if( deg[e] )
			{
				x = e ;
				break ;
			}

		if( (--deg[x] ) == 1 ) fila.insert(x) ;

		for(int i = 9 ; i >= 0 ; i-- )
			encode_bit( isOn(i, x) ) ;
			
	}  

/*	lp(i,0,nv)
		for(auto e : tree[i] )
		{
			if( i > e ) continue ;

			for(int j = 9 ;j >= 0 ; j-- )
				encode_bit( isOn(j,i) ) ;

			for(int j = 9 ; j >= 0 ; j-- )
				encode_bit( isOn(j,e) ) ;

		}      */

//	freopen("out_encode.txt", "w", stdout ) ;
	/*debug("Arvore que recebi\n" ) ;
	for(int i = 0 ; i < nv ; i++ )
		for(auto e : tree[i] ) if( i < e ) debug("%d %d\n", i, e ) ; */

	pot[0].a.pb(1) ;
	for(int i = 1 ; i <= 998 ; i++ ) 
	{
		pot[i] = pot[i-1] + pot[i-1] ;
		pot[i] = pot[i] + pot[i-1] ;
	}

	bignum big ;

	for(int i = 0 ; i < nh ; i++ )
	{
		runBfs(i) ;

		if( i != 0 )
			for(int j = 9 ; j >= 0 ; j-- )
				encode_bit( isOn(j,dist[0] ) ) ;

		big.a.clear() ;				
		big.a.pb(0) ;

		for(int j = 1 , cnt = -1 ; j < nv ; j++ )
		{
			if( j == i ) continue ;

			cnt++ ;

			if( dist[j] == dist[ par[j] ]-1 ) continue ;

			big = big + pot[cnt] ;

			if( dist[j] == dist[ par[j] ]+1 ) big = big + pot[cnt] ;
		}

		/*for(auto e : big.a ) cout << e <<" " ;
		cout << endl ; */

		for(int j = 0 ; j < 1590 ; j++ )
		{
			if( j >= sz(big.a) ) encode_bit(0) ;
			else encode_bit( big.a[j] ) ;
		}					
	}

}

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

#define debug printf
#define lp(i,a,b) for(int i = a; i < b ; i++ )
#define ll long long
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define pii pair<int,int>

const int MAXN = 1010 ;
const int BASE = 2 ;

using namespace std ;

struct bignum
{
	vector<int> a ;
  
	void trim() 
	{
		while( sz(a) > 0 && a.back() == 0 ) a.pop_back() ;
	}
 
	bignum operator + (bignum other) const
	{
		bignum aux ;
 
		for(int i = 0 , carry = 0 ; i < max(sz(other.a), sz(a)) || carry ; i++ )
		{
			int addOther = (i >= sz(other.a) ) ? 0 : other.a[i] ;
			int addThis = (i >= sz(a) ) ? 0 : a[i] ;
 
			aux.a.push_back( addOther + addThis + carry ) ;
 
			carry = ( aux.a.back() >= BASE ) ;
 
			if(carry) aux.a.back() -= BASE ;
 
		}
 
		return aux ;
 
	}
 
	bool operator < ( bignum other ) const 
	{
		if( sz(a) != sz(other.a) ) return sz(a) < sz(other.a) ;
 
		for(int i = sz(a) - 1 ; i >= 0 ; i-- )
			if( a[i] != other.a[i] ) return a[i] < other.a[i] ;
 
	 	return false ;
	}
 
	bool operator == (bignum other) const  
	{
		return !(*this < other) && !(other < *this) ;
	}
 
	bool operator <= (bignum other) { return !(other < *this ) ; }
 
	bignum operator - (bignum other )const 
	{
		bignum aux ;
 
		for(int i = 0 ,carry=0 ; i < max(sz(a), sz(other.a) )  ; i++ )
		{
 
			int myNumber = ( i >= sz(a) ) ? 0 : a[i] ;
			int otherNumber = ( i >= sz(other.a) ) ? 0 : other.a[i] ;
 
			aux.a.push_back( myNumber - otherNumber - carry ) ;
 
			carry = ( aux.a.back() < 0 ) ;
 
			if(carry ) aux.a.back() += BASE ;
 
		}
 
		aux.trim() ;
		return aux ;
 
	}
 
} ;

static bignum pot[1000] ;
static vector<int> tree[MAXN] ;
static int dist[MAXN] , par[MAXN] ;
static bool vis[MAXN] ;
int id[MAXN] , v[MAXN] ;

void dfs2(int x)
{
	vis[x] = true ;
	for(auto e : tree[x] )
	{
		if( vis[e] ) continue ;
		par[e] = x ;
		dfs2(e) ;
	}
}

void dfs3(int x)
{
	if( x && id[x] != -1 )
	{
		if( v[ id[x] ] == 0 ) dist[x] = dist[ par[x] ]-1 ;
		else if( v[ id[x] ] == 1 ) dist[x] = dist[ par[x] ] ;
		else dist[x] = dist[ par[x] ] + 1 ;
	}

	for(auto e : tree[x] )
	{
		if( e == par[x] ) continue ;
		dfs3(e) ;
	}
}

void decode(int nv, int nh) 
{
	vector<int> prufer( nv-2, 0) ;

	for(int i = 0 ; i < nv-2 ; i++ )
		for(int j = 9 ; j >= 0 ; j-- )
			if( decode_bit() ) prufer[i] += (1<<j) ;

	vector<int> deg(nv, 1) ;
	for(auto e : prufer ) deg[e]++ ;

	set<int> s ;
	for(int i = 0 ; i < nv ; i++ )
		if( deg[i] == 1 ) s.insert(i) ;

	for(auto e : prufer )
	{
		int x = *s.begin() ;
		s.erase( s.begin() ) ;

		tree[x].pb(e) ;
		tree[e].pb(x) ;

		if( (--deg[e]) == 1 ) s.insert(e) ;

	}

	tree[ *s.begin() ].pb( nv-1 ) ;
	tree[ nv-1 ].pb( *s.begin() ) ;

/*	for(int i = 0 ; i < nv-1; i++ )
	{
		int a = 0 , b = 0 ;
		for(int j = 9 ; j >= 0 ; j-- )
			if( decode_bit() ) a += (1<<j) ;

		for(int j = 9 ; j >= 0 ; j-- )
			if( decode_bit() ) b += (1<<j) ;

		tree[a].pb(b) ;
		tree[b].pb(a) ;
	}   */


	//freopen("out_decode.txt", "w", stdout) ;
/*	debug("Arvore que recebi\n") ;
	for(int i = 0 ; i < nv ; i++ )
		for(auto e : tree[i] ) if( i < e ) debug("%d %d\n", i, e ) ; */

	dfs2(0) ;

	pot[0].a.pb(1) ;
	for(int i = 1 ; i <= 998 ; i++ )
	{
		pot[i] = pot[i-1] + pot[i-1] ;
		pot[i] = pot[i] + pot[i-1] ;
	}

	bignum big ;

	for(int i = 0 ; i < nh ; i++ )
	{

	   big.a.clear() ;
		
		dist[0] = dist[i] = 0 ;

		if(i != 0 )
			for(int j = 9 ; j >= 0 ; j-- )
				if( decode_bit() ) dist[0] += (1<<j) ;

		for(int i = 0 ; i < 1590 ; i++ ) big.a.pb( decode_bit() ) ;
		big.trim() ;
		

		for(int j = nv-2 ; j >= 0 ; j-- )
		{
			v[j] = 0 ;

			while( pot[j] <= big )
			{
				v[j]++ ;
				big = big - pot[j] ;
			}								
		}

		for(int j = 1 , cnt = 0 ; j < nv ; j++)
		{
			if(j == i ) { id[j] = -1 ; continue ; }

			id[j] = cnt ;

			cnt++ ;
		}

		dfs3(0) ;

		for(int j = 0 ; j < nv ; j++ ) hops(i, j, dist[j] ) ;

		 
	}		

}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 19704 KB Output is correct - 67570 call(s) of encode_bit()
2 Correct 51 ms 14048 KB Output is correct - 4820 call(s) of encode_bit()
3 Correct 683 ms 15312 KB Output is correct - 66570 call(s) of encode_bit()
4 Correct 52 ms 14500 KB Output is correct - 8020 call(s) of encode_bit()
5 Correct 667 ms 15264 KB Output is correct - 66570 call(s) of encode_bit()
6 Correct 802 ms 15196 KB Output is correct - 67570 call(s) of encode_bit()
7 Correct 810 ms 15640 KB Output is correct - 67570 call(s) of encode_bit()
8 Correct 766 ms 15464 KB Output is correct - 67180 call(s) of encode_bit()
9 Correct 1338 ms 15192 KB Output is correct - 67570 call(s) of encode_bit()
10 Correct 1363 ms 15540 KB Output is correct - 67570 call(s) of encode_bit()
11 Correct 1269 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
12 Correct 1166 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
13 Correct 935 ms 16192 KB Output is correct - 67570 call(s) of encode_bit()
14 Correct 904 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
15 Correct 921 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
16 Correct 1020 ms 15592 KB Output is correct - 67570 call(s) of encode_bit()
17 Correct 1055 ms 15880 KB Output is correct - 67570 call(s) of encode_bit()
18 Correct 923 ms 15976 KB Output is correct - 67570 call(s) of encode_bit()
19 Correct 878 ms 15696 KB Output is correct - 67570 call(s) of encode_bit()
20 Correct 798 ms 16120 KB Output is correct - 67570 call(s) of encode_bit()
21 Correct 866 ms 16256 KB Output is correct - 67570 call(s) of encode_bit()
22 Correct 872 ms 15656 KB Output is correct - 67570 call(s) of encode_bit()
23 Correct 879 ms 16464 KB Output is correct - 67570 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 19704 KB Output is correct - 67570 call(s) of encode_bit()
2 Correct 51 ms 14048 KB Output is correct - 4820 call(s) of encode_bit()
3 Correct 683 ms 15312 KB Output is correct - 66570 call(s) of encode_bit()
4 Correct 52 ms 14500 KB Output is correct - 8020 call(s) of encode_bit()
5 Correct 667 ms 15264 KB Output is correct - 66570 call(s) of encode_bit()
6 Correct 802 ms 15196 KB Output is correct - 67570 call(s) of encode_bit()
7 Correct 810 ms 15640 KB Output is correct - 67570 call(s) of encode_bit()
8 Correct 766 ms 15464 KB Output is correct - 67180 call(s) of encode_bit()
9 Correct 1338 ms 15192 KB Output is correct - 67570 call(s) of encode_bit()
10 Correct 1363 ms 15540 KB Output is correct - 67570 call(s) of encode_bit()
11 Correct 1269 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
12 Correct 1166 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
13 Correct 935 ms 16192 KB Output is correct - 67570 call(s) of encode_bit()
14 Correct 904 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
15 Correct 921 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
16 Correct 1020 ms 15592 KB Output is correct - 67570 call(s) of encode_bit()
17 Correct 1055 ms 15880 KB Output is correct - 67570 call(s) of encode_bit()
18 Correct 923 ms 15976 KB Output is correct - 67570 call(s) of encode_bit()
19 Correct 878 ms 15696 KB Output is correct - 67570 call(s) of encode_bit()
20 Correct 798 ms 16120 KB Output is correct - 67570 call(s) of encode_bit()
21 Correct 866 ms 16256 KB Output is correct - 67570 call(s) of encode_bit()
22 Correct 872 ms 15656 KB Output is correct - 67570 call(s) of encode_bit()
23 Correct 879 ms 16464 KB Output is correct - 67570 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 19704 KB Output is correct - 67570 call(s) of encode_bit()
2 Correct 51 ms 14048 KB Output is correct - 4820 call(s) of encode_bit()
3 Correct 683 ms 15312 KB Output is correct - 66570 call(s) of encode_bit()
4 Correct 52 ms 14500 KB Output is correct - 8020 call(s) of encode_bit()
5 Correct 667 ms 15264 KB Output is correct - 66570 call(s) of encode_bit()
6 Correct 802 ms 15196 KB Output is correct - 67570 call(s) of encode_bit()
7 Correct 810 ms 15640 KB Output is correct - 67570 call(s) of encode_bit()
8 Correct 766 ms 15464 KB Output is correct - 67180 call(s) of encode_bit()
9 Correct 1338 ms 15192 KB Output is correct - 67570 call(s) of encode_bit()
10 Correct 1363 ms 15540 KB Output is correct - 67570 call(s) of encode_bit()
11 Correct 1269 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
12 Correct 1166 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
13 Correct 935 ms 16192 KB Output is correct - 67570 call(s) of encode_bit()
14 Correct 904 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
15 Correct 921 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
16 Correct 1020 ms 15592 KB Output is correct - 67570 call(s) of encode_bit()
17 Correct 1055 ms 15880 KB Output is correct - 67570 call(s) of encode_bit()
18 Correct 923 ms 15976 KB Output is correct - 67570 call(s) of encode_bit()
19 Correct 878 ms 15696 KB Output is correct - 67570 call(s) of encode_bit()
20 Correct 798 ms 16120 KB Output is correct - 67570 call(s) of encode_bit()
21 Correct 866 ms 16256 KB Output is correct - 67570 call(s) of encode_bit()
22 Correct 872 ms 15656 KB Output is correct - 67570 call(s) of encode_bit()
23 Correct 879 ms 16464 KB Output is correct - 67570 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1039 ms 19704 KB Output is correct - 67570 call(s) of encode_bit()
2 Correct 51 ms 14048 KB Output is correct - 4820 call(s) of encode_bit()
3 Correct 683 ms 15312 KB Output is correct - 66570 call(s) of encode_bit()
4 Correct 52 ms 14500 KB Output is correct - 8020 call(s) of encode_bit()
5 Correct 667 ms 15264 KB Output is correct - 66570 call(s) of encode_bit()
6 Correct 802 ms 15196 KB Output is correct - 67570 call(s) of encode_bit()
7 Correct 810 ms 15640 KB Output is correct - 67570 call(s) of encode_bit()
8 Correct 766 ms 15464 KB Output is correct - 67180 call(s) of encode_bit()
9 Correct 1338 ms 15192 KB Output is correct - 67570 call(s) of encode_bit()
10 Correct 1363 ms 15540 KB Output is correct - 67570 call(s) of encode_bit()
11 Correct 1269 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
12 Correct 1166 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
13 Correct 935 ms 16192 KB Output is correct - 67570 call(s) of encode_bit()
14 Correct 904 ms 15072 KB Output is correct - 67570 call(s) of encode_bit()
15 Correct 921 ms 15356 KB Output is correct - 67570 call(s) of encode_bit()
16 Correct 1020 ms 15592 KB Output is correct - 67570 call(s) of encode_bit()
17 Correct 1055 ms 15880 KB Output is correct - 67570 call(s) of encode_bit()
18 Correct 923 ms 15976 KB Output is correct - 67570 call(s) of encode_bit()
19 Correct 878 ms 15696 KB Output is correct - 67570 call(s) of encode_bit()
20 Correct 798 ms 16120 KB Output is correct - 67570 call(s) of encode_bit()
21 Correct 866 ms 16256 KB Output is correct - 67570 call(s) of encode_bit()
22 Correct 872 ms 15656 KB Output is correct - 67570 call(s) of encode_bit()
23 Correct 879 ms 16464 KB Output is correct - 67570 call(s) of encode_bit()