oj.uz

Submission #414815

# Submission time Handle Problem Language Result Execution time Memory
414815 2021-05-31T08:25:56 Z amoo_safar City (JOI17_city) C++17
91 / 100
 540 ms 42404 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 30e4;
const int bl = 200;
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 = false;
	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 = 200;
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 8956 KB Output is correct
2 Correct 20 ms 8852 KB Output is correct
3 Correct 20 ms 8832 KB Output is correct
4 Correct 20 ms 8816 KB Output is correct
5 Correct 20 ms 8828 KB Output is correct
6 Correct 20 ms 8968 KB Output is correct
7 Correct 20 ms 8956 KB Output is correct
8 Correct 20 ms 8832 KB Output is correct
9 Correct 20 ms 8864 KB Output is correct
10 Correct 20 ms 8864 KB Output is correct
11 Correct 20 ms 8812 KB Output is correct
12 Correct 20 ms 8856 KB Output is correct

Subtask #2
83.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 17372 KB Output is correct - L = 1263201
2 Correct 212 ms 17516 KB Output is correct - L = 1296359
3 Correct 248 ms 17356 KB Output is correct - L = 1315307
4 Correct 224 ms 17352 KB Output is correct - L = 830554
5 Partially correct 540 ms 41512 KB Output is partially correct - L = 466676609
6 Partially correct 480 ms 41476 KB Output is partially correct - L = 466010270
7 Partially correct 505 ms 41328 KB Output is partially correct - L = 468552460
8 Partially correct 495 ms 41080 KB Output is partially correct - L = 303543802
9 Correct 447 ms 42404 KB Output is correct - L = 46604185
10 Correct 413 ms 42216 KB Output is correct - L = 4564889
11 Correct 445 ms 42132 KB Output is correct - L = 503701
12 Correct 465 ms 42084 KB Output is correct - L = 91583
13 Correct 454 ms 41780 KB Output is correct - L = 223545347
14 Partially correct 476 ms 41580 KB Output is partially correct - L = 359846206
15 Correct 219 ms 17404 KB Output is correct - L = 1274254
16 Correct 212 ms 17444 KB Output is correct - L = 1290044
17 Correct 219 ms 17576 KB Output is correct - L = 1285307
18 Partially correct 460 ms 41624 KB Output is partially correct - L = 404225580
19 Partially correct 459 ms 41836 KB Output is partially correct - L = 397131133
20 Partially correct 476 ms 41852 KB Output is partially correct - L = 394563678
21 Partially correct 471 ms 41668 KB Output is partially correct - L = 312567787
22 Partially correct 528 ms 41568 KB Output is partially correct - L = 391533577
23 Partially correct 490 ms 41468 KB Output is partially correct - L = 391445153
24 Partially correct 525 ms 41656 KB Output is partially correct - L = 393976290
25 Partially correct 495 ms 41552 KB Output is partially correct - L = 395157382
26 Partially correct 504 ms 41368 KB Output is partially correct - L = 394528940
27 Partially correct 516 ms 41288 KB Output is partially correct - L = 397735889