Submission #936222

#	Time	Username	Problem	Language	Result	Execution time	Memory
936222		nguyentunglam	City (JOI17_city)	C++17	100 / 100	370 ms	54168 KiB

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 (stderr)

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 / 8
• Subtask 2: 92 / 92