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

Ali
Benjamin

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

Subtask #1
15.0 / 15.0

#	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

Subtask #2
64.0 / 85.0

#	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

Submission #975235

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 64.0 / 85.0

Subtask #1
15.0 / 15.0

Subtask #2
64.0 / 85.0