oj.uz

Submission #218094

# Submission time Handle Problem Language Result Execution time Memory
218094 2020-04-01T07:42:05 Z patrikpavic2 City (JOI17_city) C++17
8 / 100
 719 ms 121552 KB 
#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] + (1LL << 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;
			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;
	dfs_triv(0, 0);
	dfs(0, 0);
}


















#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 15 ms 24320 KB Output is correct
2 Correct 15 ms 24320 KB Output is correct
3 Correct 15 ms 24304 KB Output is correct
4 Correct 15 ms 24320 KB Output is correct
5 Correct 15 ms 24320 KB Output is correct
6 Correct 15 ms 24320 KB Output is correct
7 Correct 15 ms 24320 KB Output is correct
8 Correct 16 ms 24320 KB Output is correct
9 Correct 15 ms 24320 KB Output is correct
10 Correct 15 ms 24320 KB Output is correct
11 Correct 17 ms 24320 KB Output is correct
12 Correct 16 ms 24320 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 35568 KB Output is correct - L = 58935
2 Correct 234 ms 34456 KB Output is correct - L = 269799
3 Correct 251 ms 34544 KB Output is correct - L = 24350
4 Correct 226 ms 34544 KB Output is correct - L = 1023
5 Partially correct 623 ms 80624 KB Output is partially correct - L = 671085567
6 Partially correct 627 ms 79928 KB Output is partially correct - L = 284030958
7 Partially correct 628 ms 79856 KB Output is partially correct - L = 408939951
8 Correct 617 ms 79088 KB Output is correct - L = 262143
9 Partially correct 679 ms 106960 KB Output is partially correct - L = 68719476735
10 Partially correct 719 ms 121408 KB Output is partially correct - L = 68719476733
11 Partially correct 686 ms 121552 KB Output is partially correct - L = 68719476223
12 Partially correct 679 ms 121552 KB Output is partially correct - L = 68719473471
13 Partially correct 644 ms 106424 KB Output is partially correct - L = 34359738367
14 Partially correct 644 ms 97264 KB Output is partially correct - L = 17179869183
15 Correct 241 ms 38384 KB Output is correct - L = 40383
16 Correct 235 ms 38384 KB Output is correct - L = 179967
17 Correct 236 ms 38384 KB Output is correct - L = 35197
18 Incorrect 634 ms 102368 KB Wrong Answer [6]
19 Halted 0 ms 0 KB -