oj.uz

Submission #414769

# Submission time Handle Problem Language Result Execution time Memory
414769 2021-05-31T07:34:01 Z amoo_safar City (JOI17_city) C++17
8 / 100
 500 ms 42060 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 300000;
const int bl = 110;

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 = 110;

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 20 ms 8856 KB Output is correct
2 Correct 20 ms 8856 KB Output is correct
3 Correct 20 ms 8852 KB Output is correct
4 Correct 20 ms 8776 KB Output is correct
5 Correct 19 ms 8840 KB Output is correct
6 Correct 19 ms 8840 KB Output is correct
7 Correct 19 ms 8936 KB Output is correct
8 Correct 19 ms 8864 KB Output is correct
9 Correct 19 ms 8808 KB Output is correct
10 Correct 19 ms 8828 KB Output is correct
11 Correct 20 ms 8808 KB Output is correct
12 Correct 19 ms 8736 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 17636 KB Output is correct - L = 666162
2 Correct 210 ms 17336 KB Output is correct - L = 658698
3 Correct 208 ms 17280 KB Output is correct - L = 659631
4 Correct 220 ms 17404 KB Output is correct - L = 667095
5 Correct 477 ms 41472 KB Output is correct - L = 245650503
6 Correct 481 ms 41332 KB Output is correct - L = 251678616
7 Correct 489 ms 41440 KB Output is correct - L = 247015482
8 Correct 500 ms 41208 KB Output is correct - L = 258304782
9 Incorrect 408 ms 42060 KB Wrong Answer [6]
10 Halted 0 ms 0 KB -