oj.uz

Submission #684183

# Submission time Handle Problem Language Result Execution time Memory
684183 2023-01-20T15:32:09 Z rainboy City (JOI17_city) C++17
30 / 100
 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)
      |                     ~~^~~

Subtask #1
8.0 / 8.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

Subtask #2
22.0 / 92.0

# 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