Submission #218091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
218091	2020-04-01T07:38:35 Z	patrikpavic2	City (JOI17_city)	C++17	8 / 100	771 ms	118744 KB

Encoder

#include "Encoder.h"
#include <vector>
#include <cstdio>
#include <set>

#define PB push_back
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair < int , int > pii;

const int N = 5e5 + 500;

vector < int > v[N];
int d0[N], d1[N], sub[N], dulj[N], nw = 0, n;
ll tko[N], jos[N];
set < pii > S;

void dfs_triv(int x,int lst){
	sub[x] = 1;
	for(int y : v[x]){
		if(y != lst){
			dfs_triv(y, x); 
			sub[x] += sub[y];
		}
	}
}

void glupi(int x){
	if(x <= n) return;
	tko[d0[x]] = tko[x];
	dulj[d0[x]] = dulj[x] + 1;
	tko[d1[x]] = tko[x] + (1 << dulj[x]); 
	dulj[d1[x]] = dulj[x] + 1;
	glupi(d0[x]); glupi(d1[x]);
}


void dfs(int x, int lst){
	for(int y : v[x]){
		if(y == lst) continue;
		S.insert({sub[y], y});
	}
	if((int)S.size() >= 2){
		for(;S.size() > 1;){
			d0[nw] = S.begin() -> Y; S.erase(S.begin()); 
			d1[nw] = S.begin() -> Y; S.erase(S.begin()); 
			sub[nw] = sub[d0[nw]] + sub[d1[nw]]; 
			//printf("nw %d -> %d i %d\n", nw, d0[nw], d1[nw]);
			S.insert({sub[nw], nw}); nw++;
		}
		if(!S.empty()){
			int root = S.begin() -> Y; S.clear();
			tko[root] = tko[x]; dulj[root] = dulj[x];
			glupi(root);
		}
	}
	else{
		for(int y : v[x]){
			if(y == lst) continue;
			tko[y] = tko[x]; dulj[y] = dulj[x] + 1;
		}
		S.clear();
	}
	for(int y : v[x])
		if(y != lst) dfs(y, x);
	//printf("x = %d tko = %lld dulj = %d\n", x, tko[x] + (1 << dulj[x]), dulj[x]);
	Code(x, tko[x] + (1LL << dulj[x]));
}

void Encode(int nn, int u1[], int u2[]){
	n = nn;
	for(int i = 0;i + 1 < n;i++)
		v[u1[i]].PB(u2[i]),
		v[u2[i]].PB(u1[i]);
	nw = n + 1;
	dfs_triv(0, 0);
	dfs(0, 0);
}

Device

#include "Device.h"
#include <cstdio>

typedef long long ll;

void InitDevice(){
	return;
}

bool dijete(ll A, ll B){
	int dulj_A = 0, dulj_B = 0;
	for(;(1LL << dulj_A) <= A;dulj_A++);
	for(;(1LL << dulj_B) <= B;dulj_B++);
	if(dulj_A > dulj_B) return 0;
	//printf("dulj_A = %d dulj_B = %d\n", dulj_A, dulj_B);
	//printf("Je li B %lld dijete od A %lld\n", B, A);
	for(int i = 0;i + 1 < dulj_A;i++){
		if((A & (1 << i)) != (B & (1 << i)))
			return 0;
	}
	//printf("DA\n");
	return 1;
}

int Answer(ll A, ll B)
{
	if(dijete(B, A)) 
		return 0;
	if(dijete(A, B)) 
		return 1;
	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	32 ms	24296 KB	Output is correct
2	Correct	59 ms	24256 KB	Output is correct
3	Correct	16 ms	24320 KB	Output is correct
4	Correct	27 ms	24320 KB	Output is correct
5	Correct	25 ms	24320 KB	Output is correct
6	Correct	26 ms	24320 KB	Output is correct
7	Correct	16 ms	24320 KB	Output is correct
8	Correct	15 ms	24320 KB	Output is correct
9	Correct	16 ms	24320 KB	Output is correct
10	Correct	33 ms	24320 KB	Output is correct
11	Correct	18 ms	24320 KB	Output is correct
12	Correct	40 ms	24320 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	239 ms	38384 KB	Output is correct - L = 58935
2	Correct	267 ms	37296 KB	Output is correct - L = 269799
3	Correct	239 ms	38384 KB	Output is correct - L = 24350
4	Correct	258 ms	37056 KB	Output is correct - L = 1023
5	Partially correct	663 ms	90816 KB	Output is partially correct - L = 671085567
6	Partially correct	702 ms	90864 KB	Output is partially correct - L = 284030958
7	Partially correct	660 ms	90608 KB	Output is partially correct - L = 408939951
8	Correct	662 ms	90096 KB	Output is correct - L = 262143
9	Incorrect	771 ms	118744 KB	Wrong Answer [6]
10	Halted	0 ms	0 KB	-