oj.uz

Submission #414773

# Submission time Handle Problem Language Result Execution time Memory
414773 2021-05-31T07:36:15 Z amoo_safar City (JOI17_city) C++17
8 / 100
 486 ms 42232 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 300000;
const int bl = 115;

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]]);
	}
}

#include "Device.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 300000;
const int bl = 115;

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 22 ms 8812 KB Output is correct
2 Correct 20 ms 8844 KB Output is correct
3 Correct 20 ms 8856 KB Output is correct
4 Correct 20 ms 8864 KB Output is correct
5 Correct 20 ms 8788 KB Output is correct
6 Correct 20 ms 8828 KB Output is correct
7 Correct 20 ms 8836 KB Output is correct
8 Correct 20 ms 8832 KB Output is correct
9 Correct 20 ms 8852 KB Output is correct
10 Correct 20 ms 8808 KB Output is correct
11 Correct 19 ms 8832 KB Output is correct
12 Correct 20 ms 8816 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 17464 KB Output is correct - L = 694008
2 Correct 207 ms 17360 KB Output is correct - L = 686232
3 Correct 211 ms 17420 KB Output is correct - L = 687204
4 Correct 214 ms 17452 KB Output is correct - L = 694980
5 Correct 485 ms 41404 KB Output is correct - L = 255918852
6 Correct 482 ms 41524 KB Output is correct - L = 257116356
7 Correct 479 ms 41516 KB Output is correct - L = 256708116
8 Partially correct 486 ms 41076 KB Output is partially correct - L = 269102088
9 Incorrect 430 ms 42232 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -