oj.uz

답안 #414788

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414788 2021-05-31T07:55:55 Z amoo_safar City (JOI17_city) C++17
98 / 100
 536 ms 42212 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);
	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){
	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:34:6: warning: unused variable 'cnt' [-Wunused-variable]
   34 |  int cnt = 0;
      |      ^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 8832 KB Output is correct
2 Correct 20 ms 8920 KB Output is correct
3 Correct 20 ms 8784 KB Output is correct
4 Correct 19 ms 8868 KB Output is correct
5 Correct 21 ms 8820 KB Output is correct
6 Correct 20 ms 8840 KB Output is correct
7 Correct 20 ms 8840 KB Output is correct
8 Correct 19 ms 8768 KB Output is correct
9 Correct 20 ms 8868 KB Output is correct
10 Correct 20 ms 8956 KB Output is correct
11 Correct 20 ms 8840 KB Output is correct
12 Correct 20 ms 8820 KB Output is correct

Subtask #2
90.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 208 ms 17488 KB Output is correct - L = 716800
2 Correct 215 ms 17496 KB Output is correct - L = 722944
3 Correct 212 ms 17344 KB Output is correct - L = 723968
4 Correct 218 ms 17352 KB Output is correct - L = 731136
5 Partially correct 532 ms 41396 KB Output is partially correct - L = 269465600
6 Partially correct 525 ms 41468 KB Output is partially correct - L = 269140992
7 Correct 485 ms 41348 KB Output is correct - L = 268281856
8 Partially correct 491 ms 41052 KB Output is partially correct - L = 285584384
9 Partially correct 439 ms 41948 KB Output is partially correct - L = 288796672
10 Partially correct 463 ms 42212 KB Output is partially correct - L = 295135232
11 Partially correct 441 ms 42116 KB Output is partially correct - L = 295013376
12 Partially correct 477 ms 42180 KB Output is partially correct - L = 302616576
13 Partially correct 471 ms 41764 KB Output is partially correct - L = 289731584
14 Partially correct 497 ms 41596 KB Output is partially correct - L = 286904320
15 Correct 213 ms 17388 KB Output is correct - L = 726016
16 Correct 215 ms 17332 KB Output is correct - L = 720896
17 Correct 220 ms 17276 KB Output is correct - L = 718848
18 Partially correct 472 ms 41868 KB Output is partially correct - L = 294992896
19 Correct 485 ms 41616 KB Output is correct - L = 265822208
20 Correct 475 ms 41564 KB Output is correct - L = 255998976
21 Partially correct 494 ms 41592 KB Output is partially correct - L = 296161280
22 Correct 485 ms 41748 KB Output is correct - L = 256529408
23 Correct 491 ms 41792 KB Output is correct - L = 256405504
24 Correct 492 ms 41424 KB Output is correct - L = 256345088
25 Correct 490 ms 41496 KB Output is correct - L = 261211136
26 Correct 531 ms 41456 KB Output is correct - L = 261163008
27 Correct 536 ms 41324 KB Output is correct - L = 264805376