oj.uz

Submission #414814

# Submission time Handle Problem Language Result Execution time Memory
414814 2021-05-31T08:24:33 Z amoo_safar City (JOI17_city) C++17
72 / 100
 519 ms 48104 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 30e4;
const int bl = 1000;
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 = 1000;
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 8952 KB Output is correct
2 Correct 20 ms 8936 KB Output is correct
3 Correct 20 ms 8960 KB Output is correct
4 Correct 20 ms 8932 KB Output is correct
5 Correct 22 ms 8960 KB Output is correct
6 Correct 20 ms 9040 KB Output is correct
7 Correct 20 ms 9012 KB Output is correct
8 Correct 20 ms 8940 KB Output is correct
9 Correct 20 ms 9036 KB Output is correct
10 Correct 20 ms 9016 KB Output is correct
11 Correct 20 ms 8984 KB Output is correct
12 Correct 20 ms 9060 KB Output is correct

Subtask #2
64.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 17464 KB Output is correct - L = 5004801
2 Correct 211 ms 17400 KB Output is correct - L = 5098640
3 Correct 219 ms 17388 KB Output is correct - L = 5198736
4 Correct 216 ms 17452 KB Output is correct - L = 3290656
5 Partially correct 482 ms 41484 KB Output is partially correct - L = 1805481601
6 Partially correct 484 ms 47420 KB Output is partially correct - L = 1799863712
7 Partially correct 519 ms 47400 KB Output is partially correct - L = 1802872848
8 Partially correct 513 ms 47348 KB Output is partially correct - L = 1180794976
9 Correct 443 ms 48036 KB Output is correct - L = 178083296
10 Correct 413 ms 48104 KB Output is correct - L = 17329120
11 Correct 424 ms 48048 KB Output is correct - L = 1989408
12 Correct 421 ms 48104 KB Output is correct - L = 362849
13 Partially correct 455 ms 47756 KB Output is partially correct - L = 853049393
14 Partially correct 479 ms 47440 KB Output is partially correct - L = 1387480705
15 Correct 219 ms 23364 KB Output is correct - L = 5017313
16 Correct 224 ms 23324 KB Output is correct - L = 5061105
17 Correct 224 ms 23300 KB Output is correct - L = 5067361
18 Partially correct 505 ms 47780 KB Output is partially correct - L = 1507095425
19 Partially correct 490 ms 47716 KB Output is partially correct - L = 1562066897
20 Partially correct 487 ms 47672 KB Output is partially correct - L = 1563261792
21 Partially correct 484 ms 47660 KB Output is partially correct - L = 1141169472
22 Partially correct 470 ms 47500 KB Output is partially correct - L = 1550774816
23 Partially correct 472 ms 47596 KB Output is partially correct - L = 1550906192
24 Partially correct 490 ms 47396 KB Output is partially correct - L = 1557493760
25 Partially correct 498 ms 47316 KB Output is partially correct - L = 1560796928
26 Partially correct 500 ms 47360 KB Output is partially correct - L = 1562567376
27 Partially correct 510 ms 47700 KB Output is partially correct - L = 1565970640