#include "Encoder.h"
#include <bits/stdc++.h>
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
using namespace std;
typedef long long ll;
static vector<int> adj[250010];
static int seen[250010];
static int sz[250010];
set<ll> visited;
int findsz(int a)
{
if (sz[a]) return sz[a];
sz[a] = 1;
for (auto b : adj[a])
{
if (sz[b]) continue;
sz[a] += findsz(b);
}
return sz[a];
}
void dfs(int a, ll node);
void dothing(int a, ll node, vector<pair<int, int> >& children)
{
visited.insert(node);
if (children.empty()) return;
int sum = accumulate(children.begin(), children.end(), 0, [](const int &a, const pair<int, int> &b) { return a+b.first;});
int am = 0;
vector<pair<int, int> > after;
for (int i = children.size()-1; i >= 0; i--)
{
after.push_back(children[i]);
am += children[i].first;
// D("%d: here %d, %d, sum %d\n", a, am, i, sum);
children.pop_back();
if (am >= sum/2)
{
reverse(after.begin(), after.end());
assert(children.size());
if (children.size() == 1)
{
dfs(children[0].second, 2*node);
}
else dothing(a, 2*node, children);
if (after.size() == 1) dfs(after[0].second, 2*node+1);
else dothing(a, 2*node+1, after);
return;
}
}
}
void dfs(int a, ll node)
{
visited.insert(node);
vector<pair<int, int> > children;
seen[a] = 1;
Code(a, node);
D("%d: %lld\n", a, node);
for (auto b : adj[a])
{
if (seen[b]) continue;
children.push_back({sz[b], b});
}
sort(children.begin(), children.end());
if (children.size() == 1) dfs(children[0].second, 2*node);
else dothing(a, node, children);
}
map<ll, int> mxstorage;
int mxdepth(ll a)
{
if (visited.find(a) == visited.end()) return 0;
if (mxstorage.find(a) != mxstorage.end()) return mxstorage[a];
return mxstorage[a] = max(mxdepth(2*a), mxdepth(2*a+1))+1;
}
void dfs2(ll a, int depth, int alloweddepth)
{
if (visited.find(a) == visited.end()) return;
assert(depth+mxdepth(a) <= alloweddepth);
dfs2(2*a, depth+1, alloweddepth);
dfs2(2*a+1, depth+1, alloweddepth);
}
void Encode(int n, int a[], int b[])
{
for (int i = 0; i < n-1; i++)
{
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
findsz(0);
dfs(0, 1);
dfs2(1, 0, 36);
}
#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void InitDevice()
{
}
ll LOG2(ll a)
{
int ans = 0;
while (a)
{
ans++;
a/=2;
}
return ans;
}
int Answer(ll s, ll t)
{
int hei1 = LOG2(s);
int hei2 = LOG2(t);
int sbigger = hei1 < hei2;
while (hei1 > hei2) hei1--, s/=2;
while (hei1 < hei2) hei2--, t/=2;
if (s == t) return sbigger;
else return 2;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
12528 KB |
Output is correct |
2 |
Correct |
9 ms |
12528 KB |
Output is correct |
3 |
Correct |
9 ms |
12528 KB |
Output is correct |
4 |
Correct |
9 ms |
12528 KB |
Output is correct |
5 |
Correct |
9 ms |
12272 KB |
Output is correct |
6 |
Correct |
9 ms |
12272 KB |
Output is correct |
7 |
Correct |
9 ms |
12272 KB |
Output is correct |
8 |
Correct |
9 ms |
12528 KB |
Output is correct |
9 |
Correct |
9 ms |
12272 KB |
Output is correct |
10 |
Correct |
9 ms |
12528 KB |
Output is correct |
11 |
Correct |
9 ms |
12528 KB |
Output is correct |
12 |
Correct |
9 ms |
12528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
213 ms |
19744 KB |
Output is correct - L = 118577 |
2 |
Correct |
212 ms |
19896 KB |
Output is correct - L = 1040032 |
3 |
Correct |
240 ms |
19696 KB |
Output is correct - L = 64058 |
4 |
Correct |
215 ms |
19696 KB |
Output is correct - L = 1023 |
5 |
Partially correct |
1168 ms |
124656 KB |
Output is partially correct - L = 1067450362 |
6 |
Partially correct |
1154 ms |
124560 KB |
Output is partially correct - L = 1073741561 |
7 |
Partially correct |
1171 ms |
124912 KB |
Output is partially correct - L = 1064828925 |
8 |
Correct |
1164 ms |
109832 KB |
Output is correct - L = 262143 |
9 |
Partially correct |
1389 ms |
163144 KB |
Output is partially correct - L = 68719476733 |
10 |
Partially correct |
1396 ms |
166640 KB |
Output is partially correct - L = 60129542141 |
11 |
Partially correct |
1392 ms |
167192 KB |
Output is partially correct - L = 68685922301 |
12 |
Partially correct |
1378 ms |
167032 KB |
Output is partially correct - L = 68291657725 |
13 |
Partially correct |
1238 ms |
146904 KB |
Output is partially correct - L = 34359738365 |
14 |
Partially correct |
1180 ms |
133992 KB |
Output is partially correct - L = 17179869181 |
15 |
Correct |
211 ms |
19696 KB |
Output is correct - L = 65534 |
16 |
Correct |
211 ms |
19952 KB |
Output is correct - L = 261884 |
17 |
Correct |
211 ms |
19952 KB |
Output is correct - L = 57330 |
18 |
Partially correct |
1339 ms |
137360 KB |
Output is partially correct - L = 68306337789 |
19 |
Partially correct |
1363 ms |
138808 KB |
Output is partially correct - L = 17181179903 |
20 |
Partially correct |
1359 ms |
138280 KB |
Output is partially correct - L = 17180131327 |
21 |
Partially correct |
1243 ms |
139912 KB |
Output is partially correct - L = 68719476733 |
22 |
Partially correct |
1230 ms |
135864 KB |
Output is partially correct - L = 34360786881 |
23 |
Partially correct |
1224 ms |
135672 KB |
Output is partially correct - L = 34360786881 |
24 |
Partially correct |
1217 ms |
131744 KB |
Output is partially correct - L = 17180917745 |
25 |
Partially correct |
1146 ms |
128864 KB |
Output is partially correct - L = 8590983165 |
26 |
Partially correct |
1218 ms |
126904 KB |
Output is partially correct - L = 8592031729 |
27 |
Partially correct |
1220 ms |
124112 KB |
Output is partially correct - L = 4299161593 |