# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
218091 |
2020-04-01T07:38:35 Z |
patrikpavic2 |
City (JOI17_city) |
C++17 |
|
771 ms |
118744 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] + (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);
}
#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;
}
# |
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 |
# |
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 |
- |