Submission #414768

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
414768	2021-05-31T07:28:57 Z	amoo_safar	City (JOI17_city)	C++17	8 / 100	512 ms	42096 KB

Encoder

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

using namespace std;


const int N = 300000;
const int bl = 100;

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;
		uniform_int_distribution<> Amoo(1, 1ll * 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 = 100;

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	21 ms	8828 KB	Output is correct
2	Correct	20 ms	8736 KB	Output is correct
3	Correct	20 ms	8820 KB	Output is correct
4	Correct	20 ms	8968 KB	Output is correct
5	Correct	20 ms	8832 KB	Output is correct
6	Correct	20 ms	8832 KB	Output is correct
7	Correct	20 ms	8948 KB	Output is correct
8	Correct	20 ms	8832 KB	Output is correct
9	Correct	20 ms	8808 KB	Output is correct
10	Correct	23 ms	8832 KB	Output is correct
11	Correct	20 ms	8808 KB	Output is correct
12	Correct	20 ms	8868 KB	Output is correct

Subtask #2

0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	210 ms	17372 KB	Output is correct - L = 605472
2	Correct	226 ms	17392 KB	Output is correct - L = 604624
3	Correct	208 ms	17660 KB	Output is correct - L = 600384
4	Correct	212 ms	17448 KB	Output is correct - L = 606320
5	Correct	476 ms	41340 KB	Output is correct - L = 232989696
6	Correct	512 ms	41352 KB	Output is correct - L = 228876896
7	Correct	476 ms	41424 KB	Output is correct - L = 225695200
8	Correct	485 ms	41264 KB	Output is correct - L = 239682112
9	Incorrect	425 ms	42096 KB	Wrong Answer [6]
10	Halted	0 ms	0 KB	-