oj.uz

Submission #936202

# Submission time Handle Problem Language Result Execution time Memory
936202 2024-03-01T11:38:50 Z nguyentunglam City (JOI17_city) C++17
8 / 100
 344 ms 47232 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;
  assert(cnt < 1e6);
  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 13076 KB Output is correct
2 Correct 2 ms 13088 KB Output is correct
3 Correct 2 ms 13076 KB Output is correct
4 Correct 2 ms 13076 KB Output is correct
5 Correct 3 ms 13088 KB Output is correct
6 Correct 3 ms 13072 KB Output is correct
7 Correct 3 ms 13496 KB Output is correct
8 Correct 2 ms 13080 KB Output is correct
9 Correct 2 ms 13484 KB Output is correct
10 Correct 2 ms 13076 KB Output is correct
11 Correct 3 ms 13480 KB Output is correct
12 Correct 3 ms 13188 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 24840 KB Output is correct - L = 282624
2 Correct 131 ms 24888 KB Output is correct - L = 293888
3 Correct 127 ms 24728 KB Output is correct - L = 287488
4 Correct 128 ms 24648 KB Output is correct - L = 286464
5 Correct 341 ms 47232 KB Output is correct - L = 115400960
6 Correct 335 ms 46980 KB Output is correct - L = 117582592
7 Correct 344 ms 47020 KB Output is correct - L = 118278400
8 Correct 313 ms 46900 KB Output is correct - L = 132052736
9 Runtime error 124 ms 46348 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -