oj.uz

Submission #414816

# Submission time Handle Problem Language Result Execution time Memory
414816 2021-05-31T08:26:56 Z amoo_safar City (JOI17_city) C++17
8 / 100
 497 ms 41436 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 = 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 = 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 22 ms 8836 KB Output is correct
2 Correct 20 ms 8864 KB Output is correct
3 Correct 22 ms 8864 KB Output is correct
4 Correct 20 ms 8828 KB Output is correct
5 Correct 19 ms 8936 KB Output is correct
6 Correct 20 ms 8948 KB Output is correct
7 Correct 20 ms 8832 KB Output is correct
8 Correct 22 ms 8832 KB Output is correct
9 Correct 19 ms 8808 KB Output is correct
10 Correct 20 ms 8828 KB Output is correct
11 Correct 20 ms 8932 KB Output is correct
12 Correct 20 ms 8900 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 17376 KB Output is correct - L = 964405
2 Correct 221 ms 17316 KB Output is correct - L = 999320
3 Correct 244 ms 17444 KB Output is correct - L = 1007748
4 Correct 214 ms 17452 KB Output is correct - L = 633304
5 Incorrect 497 ms 41436 KB Wrong Answer [6]
6 Halted 0 ms 0 KB -