Submission #414780

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414780	2021-05-31T07:45:19 Z	amoo_safar	City (JOI17_city)	C++17	8 / 100	544 ms	41760 KB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 29e4;
const int bl = 125;

int mk[N];
mt19937 rng(58);
vector<int> V;

vector<int> G[N];
int st[N], fn[N], T = 0;

void DFS(int u, int p){
	st[u] = T ++;
	for(auto adj : G[u])
		if(adj != p)
			DFS(adj, u);
	fn[u] = T;
	while(mk[fn[u] - st[u] ] == -1){
		fn[u] ++;
		T ++;
	}
	// cerr << "!! " << u << ' ' << st[u] << ' ' << fn[u] << '\n'; 
}

void Encode(int _n, int A[], int B[]){
	memset(mk, -1, sizeof mk);
	int cnt = 0;

	for(int i = 1; i < N; i++){
		int pr = (i + bl - 1) / bl;
		// if(i > N / 2) pr += pr;
		uniform_int_distribution<> Amoo(1, pr);
		if(Amoo(rng) == 1){
			mk[i] = V.size();
			V.push_back(i);
		}
	}
	int sz = V.size();
	for(int i = 0; i < _n - 1; i++)
		G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);
	T = 0;
	DFS(0, -1);
	cerr << "! " << V.size() << '\n';
	// for(int i = 0; i < _n; i++)
		// cerr << "! " << st[i] << ' ' << fn[i] << '\n';
	
	for(int i = 0; i < _n; i++){
		Code(i, 1ll * sz * st[i] + mk[fn[i] - st[i]]);
	}
}

Device

#include "Device.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 29e4;
const int bl = 125;

mt19937 rng2(58);
vector<int> V2;

void InitDevice(){
	for(int i = 1; i < N; i++){
		int pr = (i + bl - 1) / bl;
		uniform_int_distribution<> Amoo(1, pr);

		if(Amoo(rng2) == 1)
			V2.push_back(i);
	}
}

int Answer(long long S, long long T){
	int sz = V2.size();
	int s1 = S / sz, f1 = s1 + V2[S % sz];
	int s2 = T / sz, f2 = s2 + V2[T % sz];

	if(s2 <= s1 && s1 < f2) return 0;
	if(s1 <= s2 && s2 < f1) return 1;
	return 2;
}

Compilation message

Encoder.cpp: In function 'void Encode(int, int*, int*)':
Encoder.cpp:32:6: warning: unused variable 'cnt' [-Wunused-variable]
   32 |  int cnt = 0;
      |      ^~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	8624 KB	Output is correct
2	Correct	20 ms	8516 KB	Output is correct
3	Correct	20 ms	8688 KB	Output is correct
4	Correct	20 ms	8584 KB	Output is correct
5	Correct	20 ms	8584 KB	Output is correct
6	Correct	19 ms	8576 KB	Output is correct
7	Correct	20 ms	8668 KB	Output is correct
8	Correct	20 ms	8576 KB	Output is correct
9	Correct	22 ms	8576 KB	Output is correct
10	Correct	20 ms	8576 KB	Output is correct
11	Correct	20 ms	8716 KB	Output is correct
12	Correct	20 ms	8704 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	216 ms	17064 KB	Output is correct - L = 729708
2	Correct	211 ms	16996 KB	Output is correct - L = 721532
3	Correct	208 ms	17148 KB	Output is correct - L = 722554
4	Correct	210 ms	17068 KB	Output is correct - L = 730730
5	Partially correct	490 ms	41156 KB	Output is partially correct - L = 268891266
6	Partially correct	544 ms	41064 KB	Output is partially correct - L = 268635766
7	Correct	500 ms	41392 KB	Output is correct - L = 267878464
8	Partially correct	507 ms	40896 KB	Output is partially correct - L = 281123584
9	Partially correct	509 ms	41724 KB	Output is partially correct - L = 288232616
10	Incorrect	408 ms	41760 KB	Wrong Answer [6]
11	Halted	0 ms	0 KB	-