# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
61054 |
2018-07-25T07:03:22 Z |
ainta(#1756) |
City (JOI17_city) |
C++11 |
|
601 ms |
64432 KB |
#include "Encoder.h"
#include<cstdio>
#include<algorithm>
#include<vector>
#include<map>
#define N_ 251000
using namespace std;
vector<long long>E[N_];
long long L[N_];
long long D[N_], Res[N_];
map<long long, long long>Map;
struct point {
long long l, x;
bool operator<(const point &p)const {
return l < p.l;
}
};
void DFS(long long a, long long pp) {
D[a] = L[a] = 0;
for (auto &x : E[a]) {
if (x == pp)continue;
DFS(x, a);
}
vector<point>T;
for (auto &x : E[a]) {
if (x == pp)continue;
T.push_back({ L[x],x });
}
if (T.empty()) return;
if (T.size() == 1) {
L[a] = T[0].l;
return;
}
sort(T.begin(), T.end());
long long s = 0;
for (auto &t : T) {
s += 1ll << t.l;
}
long long i;
for (i = 0;; i++) {
if ((1ll << i) >= s)break;
}
L[a] = i;
long long ss = 0;
for (i = T.size() - 1; i >= 0; i--) {
long long x = T[i].x;
long long l = T[i].l;
D[x] = (ss >> l);
ss += (1ll << l);
}
}
long long LM;
void Go(long long a, long long pp, long long g, long long l, long long dep) {
Code(a, (((g << 1) + 1) << (L[0] - l)) * 32 + dep);
for (auto &x : E[a]) {
if (x == pp)continue;
Go(x, a, (g << (L[a] - L[x])) + D[x], l + L[a] - L[x], dep+1);
}
}
void Encode(int N, int A[], int B[])
{
for (long long i = 0; i < N-1; ++i) {
E[A[i]].push_back(B[i]);
E[B[i]].push_back(A[i]);
}
DFS(0 ,-1);
Go(0, -1, 0, 0, 0);
}
#include "Device.h"
void InitDevice()
{
}
int Answer(long long S, long long T)
{
long long L1 = S & 31, L2 = T & 31;
S >>= 5, T >>= 5;
long long i, ck1 = 0, ck2 = 0;
for (i = 0;i<60; i++) {
if (ck1 && ck2 && ((S >> i) & 1) != ((T >> i) & 1))return 2;
if (!ck1) {
if ((S >> i) & 1)ck1 = i + 1;
}
if (!ck2) {
if ((T >> i) & 1)ck2 = i + 1;
}
}
if (ck1 < ck2)return 0;
if (ck1 > ck2)return 1;
if (L1 > L2)return 0;
else return 1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12544 KB |
Output is correct |
2 |
Correct |
8 ms |
12544 KB |
Output is correct |
3 |
Correct |
8 ms |
12376 KB |
Output is correct |
4 |
Correct |
9 ms |
12544 KB |
Output is correct |
5 |
Correct |
9 ms |
12544 KB |
Output is correct |
6 |
Correct |
8 ms |
12544 KB |
Output is correct |
7 |
Correct |
9 ms |
12544 KB |
Output is correct |
8 |
Correct |
8 ms |
12544 KB |
Output is correct |
9 |
Correct |
8 ms |
12544 KB |
Output is correct |
10 |
Correct |
7 ms |
12544 KB |
Output is correct |
11 |
Correct |
7 ms |
12544 KB |
Output is correct |
12 |
Correct |
9 ms |
12544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
164 ms |
19440 KB |
Output is correct - L = 139425 |
2 |
Correct |
165 ms |
19512 KB |
Output is correct - L = 262883 |
3 |
Correct |
166 ms |
19616 KB |
Output is correct - L = 225313 |
4 |
Correct |
166 ms |
19552 KB |
Output is correct - L = 24552 |
5 |
Partially correct |
592 ms |
61744 KB |
Output is partially correct - L = 1720264289 |
6 |
Partially correct |
568 ms |
61680 KB |
Output is partially correct - L = 1627720035 |
7 |
Partially correct |
596 ms |
61960 KB |
Output is partially correct - L = 2116374691 |
8 |
Correct |
601 ms |
64432 KB |
Output is correct - L = 8388593 |
9 |
Incorrect |
461 ms |
62656 KB |
Output isn't correct - L = 1099515475489 |
10 |
Halted |
0 ms |
0 KB |
- |