oj.uz

답안 #414777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414777 2021-05-31T07:40:26 Z amoo_safar City (JOI17_city) C++17
8 / 100
 524 ms 42240 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 300000;
const int bl = 120;

int mk[N];
mt19937 rng(58);
vector<int> V;

vector<int> G[N];
int st[N], fn[N], T = 0;

void DFS(int u, int p){
	st[u] = T ++;
	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 = 300000;
const int bl = 120;

mt19937 rng2(58);
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){
	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:32:6: warning: unused variable 'cnt' [-Wunused-variable]
   32 |  int cnt = 0;
      |      ^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 8812 KB Output is correct
2 Correct 19 ms 8940 KB Output is correct
3 Correct 20 ms 8732 KB Output is correct
4 Correct 20 ms 8956 KB Output is correct
5 Correct 20 ms 8856 KB Output is correct
6 Correct 22 ms 8832 KB Output is correct
7 Correct 22 ms 8808 KB Output is correct
8 Correct 22 ms 8836 KB Output is correct
9 Correct 20 ms 8832 KB Output is correct
10 Correct 20 ms 8796 KB Output is correct
11 Correct 19 ms 8820 KB Output is correct
12 Correct 20 ms 9076 KB Output is correct

Subtask #2
0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 255 ms 17308 KB Output is correct - L = 708288
2 Correct 215 ms 17320 KB Output is correct - L = 700352
3 Correct 215 ms 17400 KB Output is correct - L = 701344
4 Correct 211 ms 17416 KB Output is correct - L = 709280
5 Correct 496 ms 41436 KB Output is correct - L = 260998176
6 Correct 489 ms 41452 KB Output is correct - L = 260760096
7 Correct 504 ms 41448 KB Output is correct - L = 260689664
8 Partially correct 524 ms 41196 KB Output is partially correct - L = 274639168
9 Partially correct 433 ms 42108 KB Output is partially correct - L = 285907296
10 Partially correct 423 ms 42240 KB Output is partially correct - L = 284600832
11 Incorrect 429 ms 42172 KB Wrong Answer [6]
12 Halted 0 ms 0 KB -