#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], nww = 0, n;
ll tko[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, int duljina){
if(x < 0) return;
if(x < n){
// printf("x = %d tko = %lld dulj = %d\n", x, tko[x] + (1 << duljina), duljina);
Code(x, tko[x] + (1LL << duljina));
}
if(d0[x] >= 0)
tko[d0[x]] = tko[x];
if(d1[x] >= 0)
tko[d1[x]] = tko[x] + (1LL << duljina);
glupi(d0[x], duljina + 1); glupi(d1[x], duljina + 1);
}
void dfs(int x, int lst){
for(int y : v[x]){
if(y == lst) continue;
dfs(y, x);
}
for(int y : v[x])
if(y != lst)
S.insert({dulj[y], y});
d0[x] = -1, d1[x] = -1;
if((int)S.size() >= 2){
for(;S.size() > 1;){
int nw = nww++;
if((int)S.size() == 2)
nw = x, nww--;
d0[nw] = S.begin() -> Y; S.erase(S.begin());
d1[nw] = S.begin() -> Y; S.erase(S.begin());
dulj[nw] = max(dulj[d0[nw]], dulj[d1[nw]]) + 1;
//printf("nw = %d\n", nw);
S.insert({dulj[nw], nw});
}
}
else{
for(int y : v[x]){
if(y == lst) continue;
d0[x] = y;
dulj[x] = dulj[y] + 1;
}
}
S.clear();
}
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]);
nww = n;
dfs_triv(0, 0);
dfs(0, 0);
glupi(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 & (1LL << i)) != (B & (1LL << 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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
24320 KB |
Output is correct |
2 |
Correct |
15 ms |
24320 KB |
Output is correct |
3 |
Correct |
15 ms |
24320 KB |
Output is correct |
4 |
Correct |
16 ms |
24320 KB |
Output is correct |
5 |
Correct |
20 ms |
24320 KB |
Output is correct |
6 |
Correct |
15 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 |
15 ms |
24320 KB |
Output is correct |
10 |
Correct |
15 ms |
24320 KB |
Output is correct |
11 |
Correct |
15 ms |
24320 KB |
Output is correct |
12 |
Correct |
15 ms |
24320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
239 ms |
38384 KB |
Output is correct - L = 16383 |
2 |
Correct |
244 ms |
37360 KB |
Output is correct - L = 114431 |
3 |
Correct |
242 ms |
37360 KB |
Output is correct - L = 16383 |
4 |
Correct |
237 ms |
37104 KB |
Output is correct - L = 1023 |
5 |
Correct |
627 ms |
88048 KB |
Output is correct - L = 134217578 |
6 |
Correct |
622 ms |
88816 KB |
Output is correct - L = 134217727 |
7 |
Correct |
621 ms |
88816 KB |
Output is correct - L = 134217663 |
8 |
Correct |
597 ms |
85232 KB |
Output is correct - L = 262143 |
9 |
Partially correct |
679 ms |
117184 KB |
Output is partially correct - L = 68719476735 |
10 |
Partially correct |
691 ms |
118848 KB |
Output is partially correct - L = 68719476733 |
11 |
Partially correct |
696 ms |
117464 KB |
Output is partially correct - L = 68719476223 |
12 |
Partially correct |
679 ms |
116944 KB |
Output is partially correct - L = 68719473471 |
13 |
Partially correct |
642 ms |
103392 KB |
Output is partially correct - L = 34359738367 |
14 |
Partially correct |
634 ms |
93160 KB |
Output is partially correct - L = 17179869183 |
15 |
Correct |
241 ms |
38384 KB |
Output is correct - L = 32767 |
16 |
Correct |
246 ms |
38384 KB |
Output is correct - L = 131071 |
17 |
Correct |
239 ms |
37616 KB |
Output is correct - L = 32255 |
18 |
Partially correct |
648 ms |
100312 KB |
Output is partially correct - L = 34359400255 |
19 |
Partially correct |
654 ms |
101096 KB |
Output is partially correct - L = 34358108160 |
20 |
Partially correct |
647 ms |
101088 KB |
Output is partially correct - L = 34294005760 |
21 |
Partially correct |
637 ms |
96992 KB |
Output is partially correct - L = 34359672831 |
22 |
Partially correct |
642 ms |
92608 KB |
Output is partially correct - L = 34358460416 |
23 |
Partially correct |
640 ms |
92640 KB |
Output is partially correct - L = 34358460416 |
24 |
Partially correct |
643 ms |
89584 KB |
Output is partially correct - L = 17175969792 |
25 |
Partially correct |
641 ms |
88304 KB |
Output is partially correct - L = 17172496384 |
26 |
Partially correct |
649 ms |
87280 KB |
Output is partially correct - L = 8588656640 |
27 |
Partially correct |
659 ms |
86288 KB |
Output is partially correct - L = 4292378624 |