Submission #958404

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
958404	2024-04-05T18:23:15 Z	Soumya1	City (JOI17_city)	C++17	8 / 100	328 ms	53952 KB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 250'000 + 5;
vector<int> ad[mxN];
int timer;
int in[mxN], sz[mxN], out[mxN];
void dfs(int u, int p) {
	in[u] = ++timer;
	sz[u] = 1;
	for (int v : ad[u]) {
		if (v == p) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
	int val = 1, power = 0;
	while (val < sz[u]) {
		val = ceil((double) 1.5 * val);
		power++;
	}
	timer += val - sz[u];
	sz[u] = val;
	out[u] = power;
}
void Encode(int N, int A[], int B[]) {
	for (int i = 0; i < N - 1; i++) {
		ad[A[i]].push_back(B[i]);
		ad[B[i]].push_back(A[i]);
	}
	dfs(0, -1);
	for (int i = 0; i < N; ++i) {
		Code(i, in[i] * 256 + out[i]);
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;
void InitDevice() {
}
int get(int x) {
	int val = 1;
	for (int i = 0; i < x; i++) val = ceil((double) 1.5 * val);
	return val;
}
int Answer(long long S, long long T) {
	int inS = S / 256, inT = T / 256;
	int outS = inS + get(S % 256), outT = inT + get(T % 256);
	if (inT <= inS && outT >= outS) return 0;
	if (inS <= inT && outS >= outT) return 1; 
	return 2;
}

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	15152 KB	Output is correct
2	Correct	2 ms	15132 KB	Output is correct
3	Correct	4 ms	15116 KB	Output is correct
4	Correct	3 ms	15384 KB	Output is correct
5	Correct	2 ms	15136 KB	Output is correct
6	Correct	3 ms	15120 KB	Output is correct
7	Correct	4 ms	15124 KB	Output is correct
8	Correct	3 ms	15136 KB	Output is correct
9	Correct	2 ms	15124 KB	Output is correct
10	Correct	2 ms	15308 KB	Output is correct
11	Correct	3 ms	15324 KB	Output is correct
12	Correct	2 ms	15136 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	137 ms	29688 KB	Output is correct - L = 491008
2	Correct	149 ms	29636 KB	Output is correct - L = 928768
3	Correct	134 ms	29744 KB	Output is correct - L = 543232
4	Correct	142 ms	29660 KB	Output is correct - L = 370688
5	Partially correct	316 ms	53952 KB	Output is partially correct - L = 830968320
6	Partially correct	305 ms	53528 KB	Output is partially correct - L = 1024412928
7	Partially correct	328 ms	53568 KB	Output is partially correct - L = 715709952
8	Partially correct	306 ms	53612 KB	Output is partially correct - L = 322521856
9	Incorrect	67 ms	29056 KB	Wrong Answer [3]
10	Halted	0 ms	0 KB	-