oj.uz

Submission #414785

# Submission time Handle Problem Language Result Execution time Memory
414785 2021-05-31T07:53:13 Z amoo_safar City (JOI17_city) C++17
8 / 100
 209 ms 17164 KB 
#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 ++;
	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 = 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:33:6: warning: unused variable 'cnt' [-Wunused-variable]
   33 |  int cnt = 0;
      |      ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 8564 KB Output is correct
2 Correct 19 ms 8484 KB Output is correct
3 Correct 19 ms 8588 KB Output is correct
4 Correct 20 ms 8600 KB Output is correct
5 Correct 20 ms 8552 KB Output is correct
6 Correct 19 ms 8552 KB Output is correct
7 Correct 19 ms 8580 KB Output is correct
8 Correct 19 ms 8576 KB Output is correct
9 Correct 20 ms 8692 KB Output is correct
10 Correct 19 ms 8580 KB Output is correct
11 Correct 20 ms 8576 KB Output is correct
12 Correct 20 ms 8552 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 209 ms 17164 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -