Submission #414776

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414776	2021-05-31T07:39:02 Z	amoo_safar	City (JOI17_city)	C++17	8 / 100	500 ms	41520 KB

Encoder

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

using namespace std;


const int N = 300000;
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 = 300000;
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;
		if(i > N / 2) pr += pr;
		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	8808 KB	Output is correct
2	Correct	20 ms	8832 KB	Output is correct
3	Correct	22 ms	8836 KB	Output is correct
4	Correct	20 ms	8860 KB	Output is correct
5	Correct	20 ms	8856 KB	Output is correct
6	Correct	20 ms	8832 KB	Output is correct
7	Correct	20 ms	8832 KB	Output is correct
8	Correct	20 ms	8824 KB	Output is correct
9	Correct	20 ms	8856 KB	Output is correct
10	Correct	20 ms	8828 KB	Output is correct
11	Correct	20 ms	8828 KB	Output is correct
12	Correct	20 ms	8836 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	225 ms	17440 KB	Output is correct - L = 698292
2	Correct	218 ms	17308 KB	Output is correct - L = 690468
3	Correct	214 ms	17572 KB	Output is correct - L = 691446
4	Correct	217 ms	17404 KB	Output is correct - L = 699270
5	Correct	497 ms	41388 KB	Output is correct - L = 257314734
6	Correct	493 ms	41364 KB	Output is correct - L = 257070234
7	Correct	491 ms	41520 KB	Output is correct - L = 256345536
8	Incorrect	500 ms	41348 KB	Wrong Answer [6]
9	Halted	0 ms	0 KB	-