Submission #975235

# Submission time Handle Problem Language Result Execution time Memory
975235 2024-05-04T15:09:24 Z nguyentunglam Flights (JOI22_flights) C++17
79 / 100
258 ms 6232 KB
#include "Ali.h"
#include <string>
#include <vector>
#include<bits/stdc++.h>
using namespace std;

namespace alice_tree {

const int N = 1e6 + 10;

int tree[N], x[30];

int cnt_tree;

void backtrack (int pos, int one, int h) {
//  cerr << pos << " " << one << " " << h << endl;
  if (one == 13) {
    int mask = 0;
    for(int i = 0; i < pos; i++) if (x[i]) mask |= (1 << i);
//    if (mask == 16373) {
//      for(int i = 0; i <= pos; i++) cout << x[i]; cout << endl;
//    }
//    for(int i = 0; i <= pos; i++) cout << x[i] << " "; cout << endl;
    int cur = 0, cnt_id = 0;
    vector<int> p(13, 0), cnt(13, 0);
    for(int i = 0; i < pos; i++) {
//      if (mask == 16373) cout << i << " " << cur << endl;
      if (x[i] == 1) {
        if (cnt[cur] >= 2) return;
        cnt[cur]++;
        p[++cnt_id] = cur;
        cur = cnt_id;
      }
      else {
        assert(cur);
        cur = p[cur];
      }
    }
    int result_mask = 0;
    for(int i = 0; i < pos; i++) if (x[i]) result_mask |= (1 << i);
    tree[cnt_tree++] = result_mask;
    return;
  }

  if (h > 0) {
    x[pos] = 0;
    backtrack(pos + 1, one, h - 1);
  }
  x[pos] = 1;
  backtrack(pos + 1, one + 1, h + 1);
}

void gen_tree () {
  backtrack(0, 1, 0);
  sort(tree, tree + cnt_tree);
}

int idx (int mask) {
  return lower_bound(tree, tree + cnt_tree, mask) - tree;
}

}

namespace alice {

const int N = 1e4 + 10, B = 7;

int par[N], idx_in_group[N], d[N], id[N];

int group_mask[2010];

int n;

int root = 0;

bool in[N];

vector<int> adj[N], g[N];

int cnt_group;

long long encode (vector<int> a, vector<int> b) {
  long long code = 0;
  for(int j = 0; j < (int) a.size(); j++) {
    code = code * b[j] + a[j];
  }
  return code;
}

vector<int> decode (long long code, vector<int> b) {
  vector<int> a(b.size());
  for(int j = b.size() - 1; j >= 0; j--) {
    a[j] = code % b[j];
    code /= b[j];
  }
  return a;
}

vector<int> dfs(int u) {
//  cout << u << endl;
  vector<int> cur;
  cur.push_back(u);
  for(int &v : adj[u]) if (v != par[u]) {
    d[v] = d[u] + 1;
    par[v] = u;
    vector<int> tmp = dfs(v);
    for(int &j : tmp) cur.push_back(j);
  }
  if (cur.size() >= 7 || u == root) {
    g[cnt_group] = cur;
    cnt_group++;
    cur.clear();
  }
  return cur;
}

void Init(int N, std::vector<int> U, std::vector<int> V)  {
  n = N;
  cnt_group = 0;
  for(int i = 0; i < n; i++) adj[i].clear(), g[i].clear();
  for(int i = 0; i < n; i++) par[i] = 0;

  for(int i = 0; i < n - 1; i++) {
    adj[U[i]].push_back(V[i]);
    adj[V[i]].push_back(U[i]);
  }
  for(int i = 0; i < n; i++) if (adj[i].size() == 1) root = i;
  d[root] = 0;
  par[root] = root;
  dfs(root);
//  exit(0);
//  cout << cnt_group << endl;
  assert(cnt_group <= 1429);

  sort(g, g + cnt_group, [] (const vector<int> &x, vector<int> &y) {
    return d[x[0]] < d[y[0]];
       });
//  for(int i = 0; i < cnt_group; i++) {
//    for(int &j : g[i]) cout << j << " "; cout << endl;
//  }

  if (alice_tree::cnt_tree == 0) alice_tree::gen_tree();
//  cout << alice_tree::cnt_tree << endl;

  int total, one, get_mask, last;

  auto calc = [&] (auto self, int u) -> void {
    idx_in_group[u] = one++;
    for(int &v : adj[u]) if (in[v] && v != par[u]) {
      get_mask |= (1 << total);
      total++;
      last = total;
      self(self, v);
    }
    total++;
  };

  for(int i = 0; i < cnt_group; i++) {
    for(int &j : g[i]) in[j] = 1;
    total = one = get_mask = last = 0;
    calc(calc, g[i][0]);
    total = last;
    for(int j = g[i].size() + 1; j <= 13; j++) {
      get_mask |= (1 << total);
      total++;
    }
//    for(int j = 0; (1 << j) <= get_mask; j++) cout << (get_mask >> j & 1);
//    cout << endl;
    group_mask[i] = get_mask;
    for(int &j : g[i]) in[j] = 0;
  }

//  for(int j = 0; j <= 20; j++) cout << (65227 >> j & 1); cout << endl;

  for(int i = 0; i < cnt_group; i++) {
    for(int &j : g[i]) {
      id[j] = i * 14 + idx_in_group[j];
    }
  }
//  for(int i = 0; i < n; i++) cout << id[i] << " "; cout << endl;

  for(int i = 0; i < n; i++) {
//    cout << id[i] << " ";
    SetID(i, id[i]);
  }

//  cout << encode({1, 2, 3}, {3, 4, 5}) << endl;

//  vector<int> tmp = decode(33, {3, 4, 5});

//  for(int &j : tmp) cout << j << " ";

//  exit(0);
}

std::string SendA(std::string S)  {
  int code = 0;
  for(int j = 0; j < 20; j++) if (S[j] == '1') code |= (1 << j);
  int X = -1, Y = -1;
  for(int last = 0; last < 1429; last++) if (last * (last + 1) / 2 + last >= code) {
    Y = last;
    X = code - last * (last + 1) / 2;
    break;
  }
  assert(X >= 0 && X <= Y && Y < 1429);
//  cout << X << " " << Y << endl;
//  exit(0);

  vector<int> cnt(n, 0);

  for(int &j : g[X]) cnt[j]++;
  for(int &j : g[Y]) cnt[j]++;

  for(int v = g[X][0];; v = par[v]) {
//    cout << v << endl;
    cnt[v]++;
    if (v == root) break;
  }
  for(int v = g[Y][0];; v = par[v]) {
//    cout << v << "@\n";
    cnt[v]++;
    if (v == root) break;
  }
  cnt[g[X][0]]--;
  cnt[g[Y][0]]--;
//  cout << cnt[3] << endl;

  int lca = root;
  for(int i = 0; i < n; i++) if (cnt[i] > 1) {
    if (d[i] > d[lca]) lca = i;
  }

  int code_lca = 0, middle = g[X][0];
  for(int &j : g[X]) {
    if (j == lca) code_lca = idx_in_group[j], middle = j;
  }

//  cout << X << " " << Y << endl;

//  cout << root << endl;

//  cout << middle << " " << lca << " " << g[Y][0] << endl;

  int dist = d[middle] + d[g[Y][0]] - 2 * d[lca];

//  cout << dist << endl;

//  cout << alice_tree::idx(group_mask[X]) << " " <<  alice_tree::idx(group_mask[Y]) << "@" << endl;

//  cout << group_mask[X] << endl;

  int tmp = alice_tree::idx(group_mask[X]);

//  cout << alice_tree::tree[tmp] << endl;
//  for(int j = 0; j < 20; j++) cout << (16373 >> j & 1); cout << endl;
//  for(int j = 0; j < 20; j++) cout << (18431 >> j & 1); cout << endl;
//  exit(0);

  assert(group_mask[X] == alice_tree::tree[tmp]);

  long long Code = encode({code_lca, dist, alice_tree::idx(group_mask[X]), alice_tree::idx(group_mask[Y])},
                         {13, n, alice_tree::cnt_tree, alice_tree::cnt_tree});

  long long max_code = encode({12, n - 1, alice_tree::cnt_tree - 1, alice_tree::cnt_tree - 1},
                         {13, n, alice_tree::cnt_tree, alice_tree::cnt_tree});

//  cout << Code << endl;

  string ret;
  for(int bit = 0; (1LL << bit) <= max_code; bit++) {
    if (Code >> bit & 1) ret.push_back('1');
    else ret.push_back('0');
  }
  return ret;
}

}

void Init(int N, std::vector<int> U, std::vector<int> V) {
  return alice::Init(N, U, V);
}

std::string SendA(std::string S) {
  return alice::SendA(S);
}
#include "Benjamin.h"
#include<bits/stdc++.h>
using namespace std;
#include <string>
#include <vector>

namespace bruno_tree {

const int N = 1e6 + 10;

int tree[N], x[30];

int cnt_tree;

void backtrack (int pos, int one, int h) {
//  cerr << pos << " " << one << " " << h << endl;
  if (one == 13) {
//    for(int i = 0; i <= pos; i++) cout << x[i] << " "; cout << endl;
    int cur = 0, cnt_id = 0;
    vector<int> p(13, 0), cnt(13, 0);
    for(int i = 0; i < pos; i++) {
      if (x[i] == 1) {
        if (cnt[cur] >= 2) return;
        cnt[cur]++;
        p[++cnt_id] = cur;
        cur = cnt_id;
      }
      else {
        assert(cur);
        cur = p[cur];
      }
    }
    int result_mask = 0;
    for(int i = 0; i < pos; i++) if (x[i]) result_mask |= (1 << i);
    tree[cnt_tree++] = result_mask;
    return;
  }

  if (h > 0) {
    x[pos] = 0;
    backtrack(pos + 1, one, h - 1);
  }
  x[pos] = 1;
  backtrack(pos + 1, one + 1, h + 1);
}

void gen_tree () {
  backtrack(0, 1, 0);
  sort(tree, tree + cnt_tree);
}

int idx (int mask) {
  return lower_bound(tree, tree + cnt_tree, mask) - tree;
}
}

struct tree {

int p[20];

vector<int> adj[20];

void extract (int mask) {
  for(int i = 0; i < 20; i++) adj[i].clear();
  int cnt_id = 0, cur = 0;
  assert(mask >> 0 & 1);
  for(int i = 0; (1 << i) <= mask; i++) {
    if (mask >> i & 1 == 1) {
      p[++cnt_id] = cur;
      adj[cnt_id].push_back(cur);
      adj[cur].push_back(cnt_id);
//      cout << cnt_id << " " << cur << endl;
      cur = cnt_id;
    }
    else {
      assert(cur);
      cur = p[cur];
    }
  }
}

int dist (int u, int pre, int destination) {
  if (destination == u) return 0;
  int ret = -1;
  for(int &v : adj[u]) if (v != pre) {
    int tmp = dist(v, u, destination);
    if (tmp != -1) ret = tmp + 1;
  }
  return ret;
}
} tree1, tree2;

namespace bruno {

int x, y, X, Y;

int n;

long long encode (vector<int> a, vector<int> b) {
  long long code = 0;
  for(int j = 0; j < a.size(); j++) {
    code = code * b[j] + a[j];
  }
  return code;
}

vector<int> decode (long long code, vector<int> b) {
  vector<int> a(b.size());
  for(int j = b.size() - 1; j >= 0; j--) {
    a[j] = code % b[j];
    code /= b[j];
  }
  return a;
}

std::string SendB(int N, int xx, int yy) {
  n = N;
  if (xx > yy) swap(xx, yy);
  X = xx / 14;
  Y = yy / 14;
  x = xx % 14;
  y = yy % 14;
//  cout << X << " " << Y << "@" << endl;
  int code = Y * (Y + 1) / 2 + X;
//  cout << code << endl;
  assert((1 << 20) > code);
  string ret;
  for(int j = 0; j < 20; j++) {
    if (code >> j & 1) ret.push_back('1');
    else ret.push_back('0');
  }
  return ret;
}

int Answer(std::string T) {
//  exit(0);
  if (bruno_tree::cnt_tree == 0) bruno_tree::gen_tree();
  long long code = 0;
  for(int j = 0; j < T.size(); j++) if (T[j] == '1') code |= (1LL << j);
  vector<int> info = decode(code,
                            {13, n, bruno_tree::cnt_tree, bruno_tree::cnt_tree});

  tree1.extract(bruno_tree::tree[info[2]]);
  tree2.extract(bruno_tree::tree[info[3]]);
//  cout << x << " " << y << endl;
//  cout << bruno_tree::tree[info[2]] << endl;
  if (X == Y) return tree1.dist(x, x, y);
//  cout << 1 << endl;
//  cout << info[2] << " " << info[3] << endl;
//  cout << x << " " << y << endl;
//  exit(0);
  int middle = info[0];
  int dist = info[1];
//  cout << middle << " " << dist << endl;
//  cout << tree1.dist(x, x, middle) << endl;
//  cout << tree2.dist(y, y, 0) << endl;
//  cout << y << endl;
//  cout << dist << endl;
  return tree1.dist(x, x, middle) + tree2.dist(y, y, 0) + dist;
}

}

std::string SendB(int N, int X, int Y) {
  return bruno::SendB(N, X, Y);
}

int Answer(std::string T) {
  return bruno::Answer(T);
}

Compilation message

grader_ali.cpp:10:8: warning: '{anonymous}::_randmem' defined but not used [-Wunused-variable]
   10 |   char _randmem[12379];
      |        ^~~~~~~~

Benjamin.cpp: In member function 'void tree::extract(int)':
Benjamin.cpp:68:23: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   68 |     if (mask >> i & 1 == 1) {
      |                     ~~^~~~
Benjamin.cpp: In function 'long long int bruno::encode(std::vector<int>, std::vector<int>)':
Benjamin.cpp:101:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int j = 0; j < a.size(); j++) {
      |                  ~~^~~~~~~~~~
Benjamin.cpp: In function 'int bruno::Answer(std::string)':
Benjamin.cpp:139:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |   for(int j = 0; j < T.size(); j++) if (T[j] == '1') code |= (1LL << j);
      |                  ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 23 ms 3300 KB Output is correct
2 Correct 23 ms 3244 KB Output is correct
3 Correct 23 ms 3084 KB Output is correct
4 Correct 23 ms 3088 KB Output is correct
5 Correct 23 ms 3240 KB Output is correct
6 Correct 28 ms 3932 KB Output is correct
7 Correct 30 ms 3912 KB Output is correct
8 Correct 35 ms 3952 KB Output is correct
9 Correct 29 ms 4144 KB Output is correct
10 Correct 40 ms 4412 KB Output is correct
11 Correct 27 ms 3984 KB Output is correct
12 Correct 30 ms 3996 KB Output is correct
13 Correct 27 ms 3688 KB Output is correct
14 Correct 27 ms 3948 KB Output is correct
15 Correct 28 ms 5220 KB Output is correct
16 Correct 28 ms 4056 KB Output is correct
# Verdict Execution time Memory Grader output
1 Partially correct 23 ms 3252 KB Output is partially correct
2 Partially correct 72 ms 6232 KB Output is partially correct
3 Partially correct 24 ms 3252 KB Output is partially correct
4 Partially correct 246 ms 4216 KB Output is partially correct
5 Partially correct 254 ms 4448 KB Output is partially correct
6 Partially correct 250 ms 4760 KB Output is partially correct
7 Partially correct 258 ms 5784 KB Output is partially correct
8 Partially correct 234 ms 4216 KB Output is partially correct
9 Partially correct 254 ms 4852 KB Output is partially correct
10 Partially correct 234 ms 5904 KB Output is partially correct
11 Partially correct 212 ms 4428 KB Output is partially correct
12 Partially correct 51 ms 4052 KB Output is partially correct
13 Partially correct 141 ms 4364 KB Output is partially correct
14 Partially correct 151 ms 4284 KB Output is partially correct
15 Partially correct 26 ms 3820 KB Output is partially correct
16 Partially correct 228 ms 5880 KB Output is partially correct
17 Partially correct 234 ms 5856 KB Output is partially correct
18 Partially correct 234 ms 5624 KB Output is partially correct
19 Partially correct 244 ms 5844 KB Output is partially correct
20 Partially correct 149 ms 5292 KB Output is partially correct
21 Partially correct 226 ms 5604 KB Output is partially correct
22 Partially correct 215 ms 4648 KB Output is partially correct
23 Partially correct 226 ms 4712 KB Output is partially correct
24 Partially correct 225 ms 4332 KB Output is partially correct
25 Partially correct 239 ms 4412 KB Output is partially correct
26 Partially correct 219 ms 4444 KB Output is partially correct
27 Partially correct 228 ms 4184 KB Output is partially correct
28 Partially correct 211 ms 4032 KB Output is partially correct
29 Partially correct 229 ms 4520 KB Output is partially correct
30 Partially correct 211 ms 4332 KB Output is partially correct
31 Partially correct 223 ms 4132 KB Output is partially correct
32 Partially correct 215 ms 4132 KB Output is partially correct
33 Partially correct 221 ms 4328 KB Output is partially correct
34 Partially correct 205 ms 4348 KB Output is partially correct
35 Partially correct 235 ms 4616 KB Output is partially correct
36 Partially correct 220 ms 4316 KB Output is partially correct
37 Partially correct 210 ms 4288 KB Output is partially correct
38 Partially correct 204 ms 4468 KB Output is partially correct
39 Partially correct 52 ms 4196 KB Output is partially correct
40 Partially correct 250 ms 5648 KB Output is partially correct