oj.uz

Submission #434263

# Submission time Handle Problem Language Result Execution time Memory
434263 2021-06-20T20:25:25 Z jhwest2 City (JOI17_city) C++14
100 / 100
 565 ms 51904 KB 
#include "Encoder.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int M = 1 << 18, N = 1 << 8;

static int n, in, A[M], B[M], K[N];
vector<int> G[M];

void dfs(int p, int cur) {
	lint l = ++in, r;
	for (int x : G[cur]) if (p != x) {
		dfs(cur, x);
	}
	int x = lower_bound(K, K + N, in + 1 - l) - K;
	in = l + K[x] - 1;
	Code(cur, (l << 8) + x);
}
void Encode(int _n, int A[], int B[]) {
	n = _n;
	for (int i = 0; i + 1 < n; i++) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	K[0] = 1;
	for (int i = 1; i < N; i++) {
		K[i] = max(K[i - 1] + 1, K[i - 1] * 21 / 20);
	}
	dfs(0, 0);
}

#include "Device.h"
#include <bits/stdc++.h>
#define va first
#define vb second
using namespace std;
typedef long long lint;
typedef pair<int, int> pint;
const int N = 1 << 8;

static int K[N];
void InitDevice()
{
	K[0] = 1;
	for (int i = 1; i < N; i++) {
		K[i] = max(K[i - 1] + 1, K[i - 1] * 21 / 20);
	}
}

int Answer(lint s, lint t)
{
	lint ls = s >> 8, rs = ls + K[s & N - 1] - 1;
	lint lt = t >> 8, rt = lt + K[t & N - 1] - 1;
	if (lt <= ls && ls <= rt) return 0;
	if (ls <= lt && lt <= rs) return 1;
	return 2;
}

Compilation message

Encoder.cpp: In function 'void dfs(int, int)':
Encoder.cpp:14:17: warning: unused variable 'r' [-Wunused-variable]
   14 |  lint l = ++in, r;
      |                 ^
Encoder.cpp: At global scope:
Encoder.cpp:10:25: warning: 'B' defined but not used [-Wunused-variable]
   10 | static int n, in, A[M], B[M], K[N];
      |                         ^
Encoder.cpp:10:19: warning: 'A' defined but not used [-Wunused-variable]
   10 | static int n, in, A[M], B[M], K[N];
      |                   ^

Device.cpp: In function 'int Answer(lint, lint)':
Device.cpp:21:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  lint ls = s >> 8, rs = ls + K[s & N - 1] - 1;
      |                                    ~~^~~
Device.cpp:22:38: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  lint lt = t >> 8, rt = lt + K[t & N - 1] - 1;
      |                                    ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6648 KB Output is correct
2 Correct 4 ms 6644 KB Output is correct
3 Correct 4 ms 6648 KB Output is correct
4 Correct 4 ms 6648 KB Output is correct
5 Correct 4 ms 6648 KB Output is correct
6 Correct 4 ms 6648 KB Output is correct
7 Correct 4 ms 6648 KB Output is correct
8 Correct 4 ms 6648 KB Output is correct
9 Correct 4 ms 6648 KB Output is correct
10 Correct 4 ms 6648 KB Output is correct
11 Correct 4 ms 6640 KB Output is correct
12 Correct 4 ms 6656 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 15248 KB Output is correct - L = 191232
2 Correct 197 ms 22120 KB Output is correct - L = 200960
3 Correct 209 ms 22288 KB Output is correct - L = 185088
4 Correct 198 ms 22152 KB Output is correct - L = 185856
5 Correct 526 ms 50840 KB Output is correct - L = 76660736
6 Correct 521 ms 51000 KB Output is correct - L = 77621248
7 Correct 565 ms 50968 KB Output is correct - L = 78296064
8 Correct 515 ms 50560 KB Output is correct - L = 85130496
9 Correct 409 ms 51784 KB Output is correct - L = 127445248
10 Correct 436 ms 51780 KB Output is correct - L = 126136064
11 Correct 402 ms 51904 KB Output is correct - L = 145971456
12 Correct 422 ms 51780 KB Output is correct - L = 132402176
13 Correct 461 ms 51320 KB Output is correct - L = 102124800
14 Correct 503 ms 50856 KB Output is correct - L = 83328768
15 Correct 198 ms 22348 KB Output is correct - L = 188672
16 Correct 220 ms 22264 KB Output is correct - L = 191488
17 Correct 200 ms 22284 KB Output is correct - L = 184320
18 Correct 476 ms 50892 KB Output is correct - L = 139021056
19 Correct 452 ms 50940 KB Output is correct - L = 64000000
20 Correct 452 ms 51040 KB Output is correct - L = 64000000
21 Correct 489 ms 51000 KB Output is correct - L = 132401920
22 Correct 494 ms 51004 KB Output is correct - L = 64463104
23 Correct 488 ms 50912 KB Output is correct - L = 64635904
24 Correct 486 ms 51152 KB Output is correct - L = 65629184
25 Correct 498 ms 50848 KB Output is correct - L = 65917952
26 Correct 491 ms 50812 KB Output is correct - L = 66733568
27 Correct 510 ms 50832 KB Output is correct - L = 66952704