Submission #414787

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414787	2021-05-31T07:54:47 Z	amoo_safar	City (JOI17_city)	C++17	8 / 100	512 ms	41848 KB

Encoder

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

using namespace std;


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

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

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

void DFS(int u, int p){
	st[u] = T ++;
	shuffle(G[u].begin(), G[u].end(), rng);
	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;
const int sd = 8585;

mt19937 rng2(sd);
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:34:6: warning: unused variable 'cnt' [-Wunused-variable]
   34 |  int cnt = 0;
      |      ^~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	8496 KB	Output is correct
2	Correct	20 ms	8700 KB	Output is correct
3	Correct	19 ms	8740 KB	Output is correct
4	Correct	19 ms	8560 KB	Output is correct
5	Correct	20 ms	8572 KB	Output is correct
6	Correct	19 ms	8552 KB	Output is correct
7	Correct	19 ms	8572 KB	Output is correct
8	Correct	20 ms	8576 KB	Output is correct
9	Correct	19 ms	8580 KB	Output is correct
10	Correct	19 ms	8580 KB	Output is correct
11	Correct	19 ms	8580 KB	Output is correct
12	Correct	20 ms	8572 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	241 ms	17160 KB	Output is correct - L = 722304
2	Correct	208 ms	17040 KB	Output is correct - L = 733590
3	Correct	245 ms	17176 KB	Output is correct - L = 733590
4	Correct	208 ms	17116 KB	Output is correct - L = 720252
5	Partially correct	495 ms	41036 KB	Output is partially correct - L = 269702568
6	Partially correct	512 ms	41308 KB	Output is partially correct - L = 277482726
7	Partially correct	503 ms	41232 KB	Output is partially correct - L = 268583202
8	Partially correct	498 ms	40816 KB	Output is partially correct - L = 275911920
9	Incorrect	465 ms	41848 KB	Wrong Answer [6]
10	Halted	0 ms	0 KB	-