oj.uz

Submission #434261

# Submission time Handle Problem Language Result Execution time Memory
434261 2021-06-20T20:21:10 Z jhwest2 City (JOI17_city) C++14
8 / 100
 196 ms 22228 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;

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;

/* 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 + (s & N - 1);
	lint lt = t >> 8, rt = lt + (t & N - 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;
      |                 ^

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6792 KB Output is correct
2 Correct 4 ms 6784 KB Output is correct
3 Correct 4 ms 6784 KB Output is correct
4 Correct 4 ms 6784 KB Output is correct
5 Correct 4 ms 6784 KB Output is correct
6 Correct 4 ms 6784 KB Output is correct
7 Correct 4 ms 6652 KB Output is correct
8 Correct 4 ms 6784 KB Output is correct
9 Correct 4 ms 6796 KB Output is correct
10 Correct 4 ms 6784 KB Output is correct
11 Correct 4 ms 6784 KB Output is correct
12 Correct 4 ms 6784 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 22228 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -