oj.uz

Submission #414767

# Submission time Handle Problem Language Result Execution time Memory
414767 2021-05-31T07:27:13 Z amoo_safar City (JOI17_city) C++17
98 / 100
 549 ms 42184 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 300000;
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;
		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 = 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 20 ms 8924 KB Output is correct
2 Correct 20 ms 8880 KB Output is correct
3 Correct 20 ms 8960 KB Output is correct
4 Correct 22 ms 8832 KB Output is correct
5 Correct 20 ms 8880 KB Output is correct
6 Correct 20 ms 8832 KB Output is correct
7 Correct 22 ms 8848 KB Output is correct
8 Correct 20 ms 8868 KB Output is correct
9 Correct 20 ms 8836 KB Output is correct
10 Correct 20 ms 8788 KB Output is correct
11 Correct 23 ms 8808 KB Output is correct
12 Correct 23 ms 8952 KB Output is correct

Subtask #2
90.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 17296 KB Output is correct - L = 731136
2 Correct 225 ms 17348 KB Output is correct - L = 722944
3 Correct 242 ms 17272 KB Output is correct - L = 723968
4 Correct 222 ms 17372 KB Output is correct - L = 732160
5 Partially correct 544 ms 41288 KB Output is partially correct - L = 269417472
6 Partially correct 506 ms 41396 KB Output is partially correct - L = 269161472
7 Correct 505 ms 41476 KB Output is correct - L = 268402688
8 Partially correct 548 ms 41100 KB Output is partially correct - L = 281673728
9 Partially correct 465 ms 42056 KB Output is partially correct - L = 288796672
10 Partially correct 448 ms 42172 KB Output is partially correct - L = 293667840
11 Partially correct 463 ms 42176 KB Output is partially correct - L = 302616576
12 Partially correct 459 ms 42184 KB Output is partially correct - L = 293628928
13 Partially correct 472 ms 41772 KB Output is partially correct - L = 289745920
14 Partially correct 507 ms 41624 KB Output is partially correct - L = 286414848
15 Correct 223 ms 17380 KB Output is correct - L = 726016
16 Correct 211 ms 17308 KB Output is correct - L = 720896
17 Correct 244 ms 17392 KB Output is correct - L = 718848
18 Partially correct 506 ms 41556 KB Output is partially correct - L = 294992896
19 Correct 509 ms 41704 KB Output is correct - L = 255998976
20 Correct 456 ms 41788 KB Output is correct - L = 255998976
21 Partially correct 475 ms 41724 KB Output is partially correct - L = 302621696
22 Correct 463 ms 41700 KB Output is correct - L = 256529408
23 Correct 471 ms 41572 KB Output is correct - L = 256405504
24 Correct 549 ms 41444 KB Output is correct - L = 256345088
25 Correct 544 ms 41504 KB Output is correct - L = 261211136
26 Correct 504 ms 41692 KB Output is correct - L = 261163008
27 Correct 491 ms 41372 KB Output is correct - L = 264805376