oj.uz

Submission #414811

# Submission time Handle Problem Language Result Execution time Memory
414811 2021-05-31T08:21:13 Z amoo_safar City (JOI17_city) C++17
8 / 100
 534 ms 47448 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 30e4;
const int bl = 125;
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);
	int fl = true;
	int 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 = 125;
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 8812 KB Output is correct
2 Correct 22 ms 8812 KB Output is correct
3 Correct 20 ms 8992 KB Output is correct
4 Correct 20 ms 8972 KB Output is correct
5 Correct 22 ms 8812 KB Output is correct
6 Correct 20 ms 8812 KB Output is correct
7 Correct 20 ms 8876 KB Output is correct
8 Correct 20 ms 8836 KB Output is correct
9 Correct 23 ms 8804 KB Output is correct
10 Correct 20 ms 8836 KB Output is correct
11 Correct 20 ms 8824 KB Output is correct
12 Correct 20 ms 8812 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 23336 KB Output is correct - L = 821249
2 Correct 242 ms 23184 KB Output is correct - L = 849920
3 Correct 221 ms 23348 KB Output is correct - L = 857088
4 Correct 222 ms 23296 KB Output is correct - L = 538624
5 Incorrect 534 ms 47448 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -