oj.uz

Submission #414825

# Submission time Handle Problem Language Result Execution time Memory
414825 2021-05-31T08:37:43 Z amoo_safar City (JOI17_city) C++17
8 / 100
 517 ms 41964 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 29e4;
const int bl = 115;
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 = 29e4;
const int bl = 115;
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 19 ms 8576 KB Output is correct
2 Correct 19 ms 8632 KB Output is correct
3 Correct 19 ms 8556 KB Output is correct
4 Correct 19 ms 8580 KB Output is correct
5 Correct 19 ms 8552 KB Output is correct
6 Correct 18 ms 8584 KB Output is correct
7 Correct 18 ms 8576 KB Output is correct
8 Correct 20 ms 8580 KB Output is correct
9 Correct 19 ms 8688 KB Output is correct
10 Correct 20 ms 8552 KB Output is correct
11 Correct 19 ms 8576 KB Output is correct
12 Correct 20 ms 8696 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 16976 KB Output is correct - L = 634380
2 Correct 211 ms 16956 KB Output is correct - L = 661540
3 Correct 211 ms 17068 KB Output is correct - L = 643110
4 Correct 212 ms 17148 KB Output is correct - L = 510220
5 Correct 492 ms 41092 KB Output is correct - L = 238728640
6 Correct 517 ms 41280 KB Output is correct - L = 238569560
7 Correct 494 ms 41108 KB Output is correct - L = 239379510
8 Correct 494 ms 40820 KB Output is correct - L = 194383150
9 Correct 429 ms 41820 KB Output is correct - L = 23593310
10 Correct 407 ms 41852 KB Output is correct - L = 2339640
11 Correct 428 ms 41964 KB Output is correct - L = 260930
12 Correct 460 ms 41920 KB Output is correct - L = 44620
13 Correct 445 ms 41568 KB Output is correct - L = 119204270
14 Correct 471 ms 41572 KB Output is correct - L = 188902650
15 Correct 217 ms 17072 KB Output is correct - L = 649900
16 Correct 211 ms 17152 KB Output is correct - L = 660570
17 Correct 240 ms 17100 KB Output is correct - L = 645050
18 Partially correct 453 ms 41292 KB Output is partially correct - L = 274719520
19 Incorrect 471 ms 41440 KB Wrong Answer [6]
20 Halted 0 ms 0 KB -