oj.uz

Submission #936199

# Submission time Handle Problem Language Result Execution time Memory
936199 2024-03-01T11:33:00 Z nguyentunglam City (JOI17_city) C++17
8 / 100
 367 ms 53952 KB 
#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;
  for(int i = 255; i >= 0; i--) if (p[i] >= cnt - st) last = i;
  assert(last < 256);
  cnt = st + p[last];
  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);
}

#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];

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

//  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 13080 KB Output is correct
3 Correct 2 ms 13072 KB Output is correct
4 Correct 2 ms 13588 KB Output is correct
5 Correct 2 ms 13084 KB Output is correct
6 Correct 2 ms 13080 KB Output is correct
7 Correct 2 ms 13584 KB Output is correct
8 Correct 2 ms 13084 KB Output is correct
9 Correct 2 ms 13580 KB Output is correct
10 Correct 2 ms 13084 KB Output is correct
11 Correct 3 ms 13072 KB Output is correct
12 Correct 2 ms 13080 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 20740 KB Output is correct - L = 282624
2 Correct 126 ms 20624 KB Output is correct - L = 293888
3 Correct 131 ms 20664 KB Output is correct - L = 287488
4 Correct 126 ms 20796 KB Output is correct - L = 286464
5 Correct 367 ms 39808 KB Output is correct - L = 115400960
6 Correct 311 ms 53256 KB Output is correct - L = 117582592
7 Correct 312 ms 53028 KB Output is correct - L = 118278400
8 Correct 321 ms 52956 KB Output is correct - L = 132052736
9 Correct 277 ms 53952 KB Output is correct - L = 264233728
10 Runtime error 127 ms 46704 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -