oj.uz

Submission #414779

# Submission time Handle Problem Language Result Execution time Memory
414779 2021-05-31T07:44:16 Z amoo_safar City (JOI17_city) C++17
8 / 100
 496 ms 40852 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 27e4;
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]]);
	}
}

#include "Device.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 27e4;
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 18 ms 7936 KB Output is correct
2 Correct 18 ms 7912 KB Output is correct
3 Correct 19 ms 8040 KB Output is correct
4 Correct 18 ms 7944 KB Output is correct
5 Correct 18 ms 8036 KB Output is correct
6 Correct 18 ms 8036 KB Output is correct
7 Correct 19 ms 7936 KB Output is correct
8 Correct 18 ms 8140 KB Output is correct
9 Correct 18 ms 7932 KB Output is correct
10 Correct 18 ms 8048 KB Output is correct
11 Correct 18 ms 7936 KB Output is correct
12 Correct 18 ms 7932 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 16680 KB Output is correct - L = 721854
2 Correct 206 ms 16496 KB Output is correct - L = 713766
3 Correct 206 ms 16608 KB Output is correct - L = 714777
4 Correct 209 ms 16636 KB Output is correct - L = 722865
5 Correct 485 ms 40852 KB Output is correct - L = 265997133
6 Correct 482 ms 40692 KB Output is correct - L = 265744383
7 Correct 496 ms 40648 KB Output is correct - L = 264995232
8 Incorrect 490 ms 40388 KB Wrong Answer [6]
9 Halted 0 ms 0 KB -