# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
684183 |
2023-01-20T15:32:09 Z |
rainboy |
City (JOI17_city) |
C++17 |
|
474 ms |
37024 KB |
#include "Encoder.h"
#include <stdlib.h>
static const int N = 250000;
static int *ej[N], eo[N];
static void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
static int ta[N], tb[N], time;
static void dfs(int p, int i) {
ta[i] = time++;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p)
dfs(i, j);
}
tb[i] = time;
}
static long long f(int a, int b) {
return (long long) b * (b - 1) / 2 + a;
}
void Encode(int n, int ii[], int jj[]) {
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int h = 0; h < n - 1; h++)
append(ii[h], jj[h]), append(jj[h], ii[h]);
time = 0, dfs(-1, 0);
for (int i = 0; i < n; i++)
Code(i, f(ta[i], tb[i]));
}
#include "Device.h"
static const int N = 250000;
void InitDevice() {}
static void g(long long x, int *a_, int *b_) {
int lower = 1, upper = N + 2;
while (upper - lower > 1) {
int b = (lower + upper) / 2;
if (x >= (long long) b * (b - 1) / 2)
lower = b;
else
upper = b;
}
*b_ = lower, *a_ = x - (long long) lower * (lower - 1) / 2;
}
int Answer(long long x, long long y) {
int tai, tbi, taj, tbj;
g(x, &tai, &tbi), g(y, &taj, &tbj);
if (taj <= tai && tbi <= tbj)
return 0;
if (tai <= taj && tbj <= tbi)
return 1;
return 2;
}
Compilation message
Encoder.cpp: In function 'void append(int, int)':
Encoder.cpp:10:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
10 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
532 KB |
Output is correct |
2 |
Correct |
0 ms |
524 KB |
Output is correct |
3 |
Correct |
0 ms |
540 KB |
Output is correct |
4 |
Correct |
0 ms |
532 KB |
Output is correct |
5 |
Correct |
0 ms |
536 KB |
Output is correct |
6 |
Correct |
0 ms |
532 KB |
Output is correct |
7 |
Correct |
0 ms |
524 KB |
Output is correct |
8 |
Correct |
0 ms |
524 KB |
Output is correct |
9 |
Correct |
0 ms |
532 KB |
Output is correct |
10 |
Correct |
0 ms |
524 KB |
Output is correct |
11 |
Correct |
1 ms |
520 KB |
Output is correct |
12 |
Correct |
0 ms |
536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
228 ms |
9100 KB |
Output is correct - L = 245349 |
2 |
Correct |
202 ms |
9092 KB |
Output is correct - L = 244649 |
3 |
Correct |
203 ms |
9000 KB |
Output is correct - L = 245349 |
4 |
Correct |
211 ms |
9112 KB |
Output is correct - L = 245349 |
5 |
Partially correct |
379 ms |
36488 KB |
Output is partially correct - L = 31250124999 |
6 |
Partially correct |
441 ms |
36504 KB |
Output is partially correct - L = 31250124999 |
7 |
Partially correct |
431 ms |
36456 KB |
Output is partially correct - L = 31250124999 |
8 |
Partially correct |
380 ms |
35784 KB |
Output is partially correct - L = 31250124999 |
9 |
Partially correct |
379 ms |
36908 KB |
Output is partially correct - L = 31250124999 |
10 |
Partially correct |
350 ms |
36936 KB |
Output is partially correct - L = 31250124999 |
11 |
Partially correct |
412 ms |
36868 KB |
Output is partially correct - L = 31250124999 |
12 |
Partially correct |
373 ms |
37024 KB |
Output is partially correct - L = 31250124999 |
13 |
Partially correct |
356 ms |
36748 KB |
Output is partially correct - L = 31250124999 |
14 |
Partially correct |
413 ms |
36604 KB |
Output is partially correct - L = 31250124999 |
15 |
Correct |
200 ms |
9240 KB |
Output is correct - L = 245349 |
16 |
Correct |
263 ms |
9096 KB |
Output is correct - L = 245349 |
17 |
Correct |
208 ms |
9104 KB |
Output is correct - L = 245349 |
18 |
Partially correct |
400 ms |
36440 KB |
Output is partially correct - L = 31250124999 |
19 |
Partially correct |
357 ms |
36324 KB |
Output is partially correct - L = 31250124999 |
20 |
Partially correct |
396 ms |
36316 KB |
Output is partially correct - L = 31250124999 |
21 |
Partially correct |
382 ms |
36540 KB |
Output is partially correct - L = 31250124999 |
22 |
Partially correct |
474 ms |
36388 KB |
Output is partially correct - L = 31250124999 |
23 |
Partially correct |
395 ms |
36392 KB |
Output is partially correct - L = 31250124999 |
24 |
Partially correct |
382 ms |
36360 KB |
Output is partially correct - L = 31250124999 |
25 |
Partially correct |
373 ms |
36364 KB |
Output is partially correct - L = 31250124999 |
26 |
Partially correct |
392 ms |
36148 KB |
Output is partially correct - L = 31250124999 |
27 |
Partially correct |
374 ms |
36120 KB |
Output is partially correct - L = 31250124999 |