Submission #958405

#	Time	Username	Problem	Language	Result	Execution time	Memory
958405		Soumya1	City (JOI17_city)	C++17	100 / 100	582 ms	54608 KiB

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 = max(val + 1, (int) ceil((double) 1.05 * 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 = max(val + 1, (int) ceil((double) 1.05 * 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 / 8
• Subtask 2: 92 / 92