Submission #975235

#	Time	Username	Problem	Language	Result	Execution time	Memory
975235		nguyentunglam	Flights (JOI22_flights)	C++17	79 / 100	258 ms	6232 KiB

Ali

#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);
}

Benjamin

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

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);
      |                  ~~^~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 64 / 85