oj.uz

Submission #414818

# Submission time Handle Problem Language Result Execution time Memory
414818 2021-05-31T08:31:57 Z amoo_safar City (JOI17_city) C++17
97 / 100
 613 ms 42392 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 30e4;
const int bl = 150;
const int sd = 58;

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 ++;
	shuffle(G[u].begin(), G[u].end(), rng);
	bool fl = true;
	bool lf = true;
	for(auto adj : G[u]) if(adj != p) lf = false;
	for(auto adj : G[u])
		if((adj != p) && ((int) G[adj].size() > 1))
			fl = false;
	if((fl) && (!lf)){
		for(auto adj : G[u]){
			if(adj != p){
				st[adj] = T;
				fn[adj] = T + 1;
			}
		}
		T ++;
	} else {
		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 = 30e4;
const int bl = 150;
const int sd = 58;

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){
	if(S == T)
		return 2;
	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:51:6: warning: unused variable 'cnt' [-Wunused-variable]
   51 |  int cnt = 0;
      |      ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 8736 KB Output is correct
2 Correct 19 ms 8812 KB Output is correct
3 Correct 19 ms 8948 KB Output is correct
4 Correct 20 ms 8832 KB Output is correct
5 Correct 20 ms 8868 KB Output is correct
6 Correct 20 ms 8828 KB Output is correct
7 Correct 20 ms 8832 KB Output is correct
8 Correct 20 ms 8832 KB Output is correct
9 Correct 20 ms 8832 KB Output is correct
10 Correct 19 ms 8964 KB Output is correct
11 Correct 20 ms 8780 KB Output is correct
12 Correct 20 ms 8932 KB Output is correct

Subtask #2
89.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 17388 KB Output is correct - L = 788620
2 Correct 229 ms 17256 KB Output is correct - L = 821128
3 Correct 229 ms 17464 KB Output is correct - L = 799456
4 Correct 228 ms 17316 KB Output is correct - L = 632100
5 Partially correct 536 ms 41484 KB Output is partially correct - L = 292924772
6 Partially correct 496 ms 41344 KB Output is partially correct - L = 292624976
7 Partially correct 562 ms 41444 KB Output is partially correct - L = 290210956
8 Correct 489 ms 41416 KB Output is correct - L = 231603848
9 Correct 489 ms 41996 KB Output is correct - L = 29290912
10 Correct 474 ms 42056 KB Output is correct - L = 2822176
11 Correct 430 ms 42392 KB Output is correct - L = 317856
12 Correct 457 ms 42084 KB Output is correct - L = 55384
13 Correct 448 ms 41804 KB Output is correct - L = 145677980
14 Correct 476 ms 41664 KB Output is correct - L = 227967768
15 Correct 222 ms 17448 KB Output is correct - L = 776580
16 Correct 265 ms 17448 KB Output is correct - L = 819924
17 Correct 265 ms 17320 KB Output is correct - L = 800660
18 Partially correct 488 ms 41564 KB Output is partially correct - L = 318066700
19 Partially correct 538 ms 41560 KB Output is partially correct - L = 305164636
20 Partially correct 530 ms 41720 KB Output is partially correct - L = 300857928
21 Correct 514 ms 41616 KB Output is correct - L = 233072728
22 Partially correct 495 ms 41828 KB Output is partially correct - L = 298547452
23 Partially correct 539 ms 41576 KB Output is partially correct - L = 299360152
24 Partially correct 613 ms 41480 KB Output is partially correct - L = 300410040
25 Partially correct 533 ms 41504 KB Output is partially correct - L = 301310632
26 Partially correct 500 ms 41508 KB Output is partially correct - L = 300831440
27 Partially correct 516 ms 41392 KB Output is partially correct - L = 305200756