Submission #1197319

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197319		sleepntsheep	한자 끝말잇기 (JOI14_kanji)	C11	0 / 100	49 ms	6984 KiB

Anna

#include "Annalib.h"
#include <stdio.h>
#include <string.h>

#define N 300
#define Q 60
#define K 5

void Anna(int n, int m, int a[], int b[], long long c[], int q, int s[], int t[], int k, int u[]) {
  static long long dp[N][N], dp2[N][N];
  unsigned long long message;
  static int ii[Q], ii_[Q], brk[K], ll[K + 1], rr[K + 1], rr_[K], ban[999999];

  memset(ban, 0, sizeof ban);
  for (int i = 0; i < k; ++i)
    ban[u[i]] = 1;
  message = 0;

  memset(dp, 0x3f, sizeof dp);
  for (int i = 0; i < n; ++i) dp[i][i] = 0;
  for (int i = 0; i < m; ++i) if (! ban[i]) dp[a[i]][b[i]] = c[i];

  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (dp[i][k] + dp[k][j] < dp[i][j])
          dp[i][j] = dp[i][k] + dp[k][j];

  for (int i = 0; i < q; ++i) {
    ii[i] = i;
  }

  ll[0] = 0;
  rr[0] = q;


  /* since we are forced to do this process forward (0-k),
   * but multiplying directly to message will reverse the order of messages sent, (stack-like)
   * Anna need to add breakpoints to message one by one, backward ordered */ 
  int gap[15], at[15], sz;
  sz = 0;

  /*https://www.luogu.com.cn/problem/solution/AT_joisc2014_l*/
  for (int p = 0; p < k; ++p) {
    for (int i_ = 0; i_ <= p; ++i_ ){
      if (i_ == 0) {
        for (int it = ll[i_]; it < rr[i_]; ++it)
          for (int j = ll[i_] + 1; j < rr[i_]; ++j)
            if (dp[s[ii[j - 1]]][t[ii[j - 1]]] > dp[s[ii[j]]][t[ii[j]]])
              ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
      } else {
        /* sort by f1 - f2, increasing since we want some suffix to have f1 - f2 > e2 - e1 */
        int bp = i_ ? b[u[i_ - 1]] : a[u[0]];
        for (int it = ll[i_]; it < rr[i_]; ++it)
          for (int j = ll[i_] + 1; j < rr[i_]; ++j)
            if (dp[bp][t[ii[j - 1]]] - dp[b[u[p]]][t[ii[j - 1]]] > dp[bp][t[ii[j]]] - dp[b[u[p]]][t[ii[j]]])
              ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
      }
    }

    for (int i_ = 0; i_ <= p; ++i_) {
      if (i_ == 0) {
        brk[i_] = rr[i_];
        for (int j = rr[i_] - 1; j >= ll[i_]; --j) {
          if (c[u[p]] + dp[s[ii[j]]][a[u[p]]] + dp[b[u[p]]][t[ii[j]]] < dp[s[ii[j]]][t[ii[j]]]) {
            //printf(" at %d, %lld better than %lld\n", p, c[u[p]] + dp[s[ii[j]]][a[u[p]]] + dp[b[u[p]]][t[ii[j]]],dp[s[ii[j]]][t[ii[j]]]);
            brk[i_] = j;
          } else
            break;
        }

      } else {
        /* since sorted by f1 - f2, we can find the breakpoint (suffix) of each interval */ 
        int bp = i_ ? b[u[i_ - 1]] : a[u[0]];
        long long ep = i_ ? c[u[i_ - 1]] : 0;

        brk[i_] = rr[i_];
        for (int j = rr[i_] - 1; j >= ll[i_]; --j) {
          /* lhs is constant, rhs is sorted */
          if (c[u[p]] - ep < dp[bp][t[ii[j]]] - dp[b[u[p]]][t[ii[j]]])
            /* beneficial to switch to new group */
            brk[i_] = j;
          else
            break;
        }
      }
      gap[sz] = rr[i_] - ll[i_] + 1;
      at[sz] = brk[i_] - ll[i_];
      ++sz;
    }

    /* move stuff */
    int qwq = 0;
    for (int i_ = 0; i_ <= p; ++i_) {
      ll[i_] = qwq;
      for (int j = ll[i_]; j < brk[i_]; ++j)
        ii_[qwq++] = ii[j];
      rr_[i_] = rr[i_];
      rr[i_] = qwq;
      //printf(" [%d] is now [%d %d)\n",i_,ll[i_],rr[i_]);
    }
    ll[p + 1] = qwq;
    for (int i_ = 0; i_ <= p; ++i_)
      for (int j = brk[i_]; j < rr_[i_]; ++j)
        ii_[qwq++] = ii[j];
    rr[p + 1] = qwq;

    memcpy(ii, ii_, sizeof ii);
  }

  while (sz) {
    --sz;
    message = message * gap[sz] + at[sz];
  }

  for (int i = 0; i < 64; ++i)
    Tap(message & 1), message >>= 1;
}

Bruno

#include "Brunolib.h"
#include <stdio.h>
#include <string.h>

#define N 300
#define Q 60
#define K 5

void PATH(int bt[N][N], int id[N][N], int s, int t) {
  if (s == t)
    return;
  if (bt[s][t] == -1) {
    Answer(id[s][t]);
    return;
  }
  PATH(bt, id, s, bt[s][t]);
  PATH(bt, id, bt[s][t], t);
}

void Bruno(int n, int m, int a[], int b[], long long c[], int q, int s[], int t[], int k, int u[], int l, int x[]) {
  static long long dp[N][N]/* shortest path with backtrack */;
  static int bt[N][N], id[N][N];
  static int ii[Q], ii_[Q], brk[K], ll[K + 1], rr[K + 1], rr_[K];
  unsigned long long message;

  message = 0;
  for (int i = 63; i >= 0; --i)
    message = (message << 1) | x[i];

  memset(bt, -1, sizeof bt);
  memset(dp, 0x3f, sizeof dp);
  for (int i = 0; i < n; ++i) dp[i][i] = 0;
  for (int i = 0; i < m; ++i) if (~ c[i])
    dp[a[i]][b[i]] = c[i], id[a[i]][b[i]] = i;

  for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (dp[i][k] + dp[k][j] < dp[i][j]) {
          dp[i][j] = dp[i][k] + dp[k][j];
          bt[i][j] = k;
        }

  for (int i = 0; i < q; ++i)
    ii[i] = i;

  ll[0] = 0;
  rr[0] = q;

  /*https://www.luogu.com.cn/problem/solution/AT_joisc2014_l*/
  for (int p = 0; p < k; ++p) {
    for (int i_ = 0; i_ <= p; ++i_ ){
      if (i_ == 0) {
        for (int it = ll[i_]; it < rr[i_]; ++it)
          for (int j = ll[i_] + 1; j < rr[i_]; ++j)
            if (dp[s[ii[j - 1]]][t[ii[j - 1]]] > dp[s[ii[j]]][t[ii[j]]])
              ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
      } else {
        /* sort by f1 - f2, increasing since we want some suffix to have f1 - f2 > e2 - e1 */
        int bp = i_ ? b[u[i_ - 1]] : a[u[0]];
        for (int it = ll[i_]; it < rr[i_]; ++it)
          for (int j = ll[i_] + 1; j < rr[i_]; ++j)
            if (dp[bp][t[ii[j - 1]]] - dp[b[u[p]]][t[ii[j - 1]]] > dp[bp][t[ii[j]]] - dp[b[u[p]]][t[ii[j]]])
              ii[j - 1] ^= ii[j], ii[j] ^= ii[j - 1], ii[j - 1] ^= ii[j];
      }
    }

    for (int i_ = 0; i_ <= p; ++i_) {
      brk[i_] = message % (rr[i_] - ll[i_] + 1);
      message /= rr[i_] - ll[i_] + 1;
    }

    /* move stuff */
    int qwq = 0;
    for (int i_ = 0; i_ <= p; ++i_) {
      ll[i_] = qwq;
      for (int j = ll[i_]; j < brk[i_]; ++j)
        ii_[qwq++] = ii[j];
      rr_[i_] = rr[i_];
      rr[i_] = qwq;
    }
    ll[p + 1] = qwq;
    for (int i_ = 0; i_ <= p; ++i_)
      for (int j = brk[i_]; j < rr_[i_]; ++j)
        ii_[qwq++] = ii[j];
    rr[p + 1] = qwq;

    memcpy(ii, ii_, sizeof ii);
  }

  /* we got all needed information to answer queries, now backtracking pain */
  for (int group, i = 0; i < q; ++i) {
    group = -1;
    for (int i_ = 0; i_ <= k; ++i_)
      if (ll[i_] <= i && i < rr[i_]) {
        group = i_;
        break;
      }
    if (!~group) __builtin_trap();

    //printf(" group = %d\n", group);

    if (! group) {
      PATH(bt, id, s[i], t[i]);
    } else {
      int a_, b_;
      if (group)
        a_ = a[u[group - 1]], b_ = b[u[group - 1]];
      else
        a_ = a[u[0]], b_ = a_;


      PATH(bt, id, s[i], a_);
      if (a_ != b_)
        Answer(id[a_][b_]);
      PATH(bt, id, b_, t[i]);
    }

    Answer(-1);
  }

}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 22
• Subtask 3: 0 / 8
• Subtask 4: 0 / 40
• Subtask 5: 0 / 20