Submission #414783

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414783	2021-05-31T07:51:10 Z	amoo_safar	City (JOI17_city)	C++17	8 / 100	569 ms	41960 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	19 ms	8552 KB	Output is correct
2	Correct	19 ms	8684 KB	Output is correct
3	Correct	22 ms	8572 KB	Output is correct
4	Correct	21 ms	8608 KB	Output is correct
5	Correct	19 ms	8696 KB	Output is correct
6	Correct	20 ms	8576 KB	Output is correct
7	Correct	20 ms	8576 KB	Output is correct
8	Correct	19 ms	8584 KB	Output is correct
9	Correct	19 ms	8576 KB	Output is correct
10	Correct	19 ms	8680 KB	Output is correct
11	Correct	20 ms	8716 KB	Output is correct
12	Correct	20 ms	8544 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	215 ms	17056 KB	Output is correct - L = 729708
2	Correct	213 ms	17056 KB	Output is correct - L = 721532
3	Correct	224 ms	17048 KB	Output is correct - L = 722554
4	Correct	227 ms	17140 KB	Output is correct - L = 730730
5	Partially correct	512 ms	41116 KB	Output is partially correct - L = 268891266
6	Partially correct	487 ms	41232 KB	Output is partially correct - L = 268635766
7	Correct	493 ms	41252 KB	Output is correct - L = 267878464
8	Partially correct	569 ms	40948 KB	Output is partially correct - L = 281123584
9	Partially correct	455 ms	41768 KB	Output is partially correct - L = 288232616
10	Incorrect	420 ms	41960 KB	Wrong Answer [6]
11	Halted	0 ms	0 KB	-