oj.uz

답안 #414840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414840 2021-05-31T08:51:47 Z amoo_safar City (JOI17_city) C++17
100 / 100
 520 ms 43072 KB 
#include "Encoder.h"
#include <bits/stdc++.h>

using namespace std;


const int N = 33e4;
const int bl = 100;
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 = false;
	for(auto adj : G[u])
		if((adj != p) && ((int) G[adj].size() == 1))
			fl = true;
	if(fl){
		for(auto adj : G[u]){
			if(adj != p && G[adj].size() == 1){
				st[adj] = T;
				fn[adj] = T + 1;
			}
		}
		T ++;
	} 
	for(auto adj : G[u])
		if(adj != p && G[adj].size() > 1)
			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 = 33e4;
const int bl = 100;
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:48:6: warning: unused variable 'cnt' [-Wunused-variable]
   48 |  int cnt = 0;
      |      ^~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 9704 KB Output is correct
2 Correct 20 ms 9604 KB Output is correct
3 Correct 22 ms 9724 KB Output is correct
4 Correct 20 ms 9580 KB Output is correct
5 Correct 22 ms 9612 KB Output is correct
6 Correct 20 ms 9684 KB Output is correct
7 Correct 23 ms 9732 KB Output is correct
8 Correct 20 ms 9704 KB Output is correct
9 Correct 24 ms 9580 KB Output is correct
10 Correct 22 ms 9712 KB Output is correct
11 Correct 20 ms 9684 KB Output is correct
12 Correct 20 ms 9692 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 18092 KB Output is correct - L = 522770
2 Correct 214 ms 18160 KB Output is correct - L = 545052
3 Correct 212 ms 18272 KB Output is correct - L = 515057
4 Correct 212 ms 18260 KB Output is correct - L = 451639
5 Correct 502 ms 42288 KB Output is correct - L = 195808217
6 Correct 485 ms 42316 KB Output is correct - L = 199624438
7 Correct 518 ms 42224 KB Output is correct - L = 197679905
8 Correct 485 ms 41956 KB Output is correct - L = 175304492
9 Correct 445 ms 42812 KB Output is correct - L = 19747851
10 Correct 430 ms 43072 KB Output is correct - L = 1914538
11 Correct 406 ms 42884 KB Output is correct - L = 227962
12 Correct 445 ms 42884 KB Output is correct - L = 35994
13 Correct 494 ms 42556 KB Output is correct - L = 96471633
14 Correct 468 ms 42336 KB Output is correct - L = 154232576
15 Correct 221 ms 18300 KB Output is correct - L = 520199
16 Correct 216 ms 18224 KB Output is correct - L = 537339
17 Correct 215 ms 18372 KB Output is correct - L = 528769
18 Correct 463 ms 42476 KB Output is correct - L = 236821666
19 Correct 469 ms 42556 KB Output is correct - L = 213172751
20 Correct 499 ms 42516 KB Output is correct - L = 214148874
21 Correct 468 ms 42548 KB Output is correct - L = 176857376
22 Correct 466 ms 42340 KB Output is correct - L = 212504291
23 Correct 481 ms 42384 KB Output is correct - L = 213082766
24 Correct 485 ms 42376 KB Output is correct - L = 214477105
25 Correct 470 ms 42224 KB Output is correct - L = 214471106
26 Correct 506 ms 42612 KB Output is correct - L = 218570994
27 Correct 520 ms 42232 KB Output is correct - L = 225579540