Submission #936222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
936222	2024-03-01T12:24:20 Z	nguyentunglam	City (JOI17_city)	C++17	100 / 100	370 ms	54168 KB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;

namespace anna {
const int NN = 3e5 + 10;
vector<int> adj[NN];
int n;
bool vis[NN];
int p[NN];
int cnt = -1;

void init () {
  p[0] = 1;
  for(int i = 1; i <= 21; i++) p[i] = i - 1;
  int cnt = 0;
  for(int i = 22; i <= 255; i++) p[i] = p[i - 1] * 21 / 20;
}

void dfs(int u) {
  vis[u] = 1;
  int st = ++cnt;
  for(int &v : adj[u]) if (!vis[v]) dfs(v);
  int last = 256;
  assert(cnt < 1e6);
  for(int i = 255; i >= 0; i--) if (p[i] >= cnt - st + 1) last = i;
//  assert(last < 256);
  cnt = st + p[last] - 1;
  long long code = st * 256 + last;
  Code(u, code);
}

void Encode(int N, int A[], int B[]) {
  n = N;
  for(int i = 0; i < N - 1; i++) {
    adj[A[i]].push_back(B[i]);
    adj[B[i]].push_back(A[i]);
  }
  init();
  for(int i = 0; i < N; i++) if (!vis[i]) dfs(i);
}

}

void Encode(int N, int A[], int B[])
{
  anna::Encode(N, A, B);
}

Device

#include "Device.h"
#include<bits/stdc++.h>
using namespace std;

int p[300];

void InitDevice()
{
  p[0] = 1;
  for(int i = 1; i <= 21; i++) p[i] = i - 1;
  int cnt = 0;
  for(int i = 22; i <= 255; i++) p[i] = p[i - 1] * 21 / 20;
}

int Answer(long long S, long long T)
{
  long long st_x = S / 256;
  long long ed_x = st_x + p[S % 256] - 1;

  long long st_y = T / 256;
  long long ed_y = st_y + p[T % 256] - 1;

//  cout << st_x << " " << ed_x << endl;
//  cout << st_y << " " << ed_y << endl;

  if (st_x <= st_y && st_y <= ed_x) return 1;
  if (st_y <= st_x && st_x <= ed_y) return 0;
	return 2;
}

Compilation message

Encoder.cpp: In function 'void anna::init()':
Encoder.cpp:17:7: warning: unused variable 'cnt' [-Wunused-variable]
   17 |   int cnt = 0;
      |       ^~~

Device.cpp: In function 'void InitDevice()':
Device.cpp:11:7: warning: unused variable 'cnt' [-Wunused-variable]
   11 |   int cnt = 0;
      |       ^~~

Subtask #1

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	13072 KB	Output is correct
2	Correct	2 ms	13336 KB	Output is correct
3	Correct	2 ms	13072 KB	Output is correct
4	Correct	2 ms	13084 KB	Output is correct
5	Correct	2 ms	13072 KB	Output is correct
6	Correct	4 ms	13072 KB	Output is correct
7	Correct	3 ms	13084 KB	Output is correct
8	Correct	2 ms	13084 KB	Output is correct
9	Correct	2 ms	13172 KB	Output is correct
10	Correct	2 ms	13068 KB	Output is correct
11	Correct	3 ms	13068 KB	Output is correct
12	Correct	2 ms	13084 KB	Output is correct

Subtask #2

92.0 / 92.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	126 ms	20820 KB	Output is correct - L = 190976
2	Correct	127 ms	20880 KB	Output is correct - L = 200704
3	Correct	130 ms	20708 KB	Output is correct - L = 184832
4	Correct	130 ms	20588 KB	Output is correct - L = 185600
5	Correct	312 ms	39676 KB	Output is correct - L = 76660480
6	Correct	328 ms	39732 KB	Output is correct - L = 77620992
7	Correct	317 ms	39568 KB	Output is correct - L = 78295808
8	Correct	326 ms	39308 KB	Output is correct - L = 85130240
9	Correct	285 ms	40480 KB	Output is correct - L = 127444992
10	Correct	297 ms	51440 KB	Output is correct - L = 126135808
11	Correct	307 ms	54168 KB	Output is correct - L = 145971200
12	Correct	313 ms	54008 KB	Output is correct - L = 132401920
13	Correct	297 ms	53604 KB	Output is correct - L = 102124544
14	Correct	309 ms	53188 KB	Output is correct - L = 83328512
15	Correct	132 ms	27708 KB	Output is correct - L = 188416
16	Correct	125 ms	27656 KB	Output is correct - L = 191232
17	Correct	126 ms	27692 KB	Output is correct - L = 184064
18	Correct	311 ms	53160 KB	Output is correct - L = 139020800
19	Correct	311 ms	53204 KB	Output is correct - L = 63999744
20	Correct	339 ms	53164 KB	Output is correct - L = 63999744
21	Correct	316 ms	53472 KB	Output is correct - L = 132401664
22	Correct	355 ms	53208 KB	Output is correct - L = 64462848
23	Correct	370 ms	53220 KB	Output is correct - L = 64635648
24	Correct	320 ms	53316 KB	Output is correct - L = 65628928
25	Correct	353 ms	53032 KB	Output is correct - L = 65917696
26	Correct	323 ms	53128 KB	Output is correct - L = 66733312
27	Correct	323 ms	53064 KB	Output is correct - L = 66952448