# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
134105 |
2019-07-22T04:50:50 Z |
AngusRitossa |
City (JOI17_city) |
C++14 |
|
681 ms |
71048 KB |
#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];
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)
{
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)
{
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);
}
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);
}
#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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
12528 KB |
Output is correct |
2 |
Correct |
9 ms |
12528 KB |
Output is correct |
3 |
Correct |
9 ms |
12536 KB |
Output is correct |
4 |
Correct |
11 ms |
12528 KB |
Output is correct |
5 |
Correct |
9 ms |
12528 KB |
Output is correct |
6 |
Correct |
9 ms |
12528 KB |
Output is correct |
7 |
Correct |
9 ms |
12528 KB |
Output is correct |
8 |
Correct |
10 ms |
12528 KB |
Output is correct |
9 |
Correct |
9 ms |
12784 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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
212 ms |
26608 KB |
Output is correct - L = 118577 |
2 |
Correct |
216 ms |
26912 KB |
Output is correct - L = 1040032 |
3 |
Correct |
222 ms |
26608 KB |
Output is correct - L = 64058 |
4 |
Correct |
204 ms |
26608 KB |
Output is correct - L = 1023 |
5 |
Partially correct |
635 ms |
69104 KB |
Output is partially correct - L = 1067450362 |
6 |
Partially correct |
645 ms |
69152 KB |
Output is partially correct - L = 1073741561 |
7 |
Partially correct |
618 ms |
69104 KB |
Output is partially correct - L = 1064828925 |
8 |
Correct |
611 ms |
68512 KB |
Output is correct - L = 262143 |
9 |
Partially correct |
636 ms |
71048 KB |
Output is partially correct - L = 68719476733 |
10 |
Partially correct |
586 ms |
70944 KB |
Output is partially correct - L = 60129542141 |
11 |
Partially correct |
563 ms |
70880 KB |
Output is partially correct - L = 68685922301 |
12 |
Partially correct |
568 ms |
70824 KB |
Output is partially correct - L = 68291657725 |
13 |
Partially correct |
614 ms |
70072 KB |
Output is partially correct - L = 34359738365 |
14 |
Partially correct |
624 ms |
69696 KB |
Output is partially correct - L = 17179869181 |
15 |
Correct |
215 ms |
26608 KB |
Output is correct - L = 65534 |
16 |
Correct |
212 ms |
26680 KB |
Output is correct - L = 261884 |
17 |
Correct |
208 ms |
26752 KB |
Output is correct - L = 57330 |
18 |
Partially correct |
621 ms |
69848 KB |
Output is partially correct - L = 68306337789 |
19 |
Partially correct |
631 ms |
69616 KB |
Output is partially correct - L = 17181179903 |
20 |
Partially correct |
679 ms |
69672 KB |
Output is partially correct - L = 17180131327 |
21 |
Partially correct |
681 ms |
70960 KB |
Output is partially correct - L = 68719476733 |
22 |
Partially correct |
668 ms |
70888 KB |
Output is partially correct - L = 34360786881 |
23 |
Partially correct |
665 ms |
70936 KB |
Output is partially correct - L = 34360786881 |
24 |
Partially correct |
651 ms |
69760 KB |
Output is partially correct - L = 17180917745 |
25 |
Partially correct |
665 ms |
69552 KB |
Output is partially correct - L = 8590983165 |
26 |
Partially correct |
652 ms |
69664 KB |
Output is partially correct - L = 8592031729 |
27 |
Partially correct |
669 ms |
69280 KB |
Output is partially correct - L = 4299161593 |