Submission #971157

#	Time	Username	Problem	Language	Result	Execution time	Memory
971157		huutuan	한자 끝말잇기 (JOI14_kanji)	C++14	100 / 100	139 ms	19060 KiB

Anna

#include "Annalib.h"

#include<bits/stdc++.h>

using namespace std;

#define int long long

static const int N=310;
static int f1[N][N], f2[N][N];
static const int inf=0x3f3f3f3f3f3f3f3f;
static int mask[60];

static mt19937 rng(69420);

void Anna(int32_t n, int32_t m, int32_t a[], int32_t b[], int c[], int32_t q, int32_t s[], int32_t t[], int32_t _k, int32_t u[]) {
   memset(f1, 0x3f, sizeof f1);
   memset(f2, 0x3f, sizeof f2);
   for (int i=0; i<m; ++i){
      f1[a[i]][b[i]]=c[i];
      f2[a[i]][b[i]]=c[i];
   }
   for (int i=0; i<_k; ++i){
      f2[a[u[i]]][b[u[i]]]=inf;
   }
   for (int i=0; i<n; ++i) f2[i][i]=0;
   for (int k=0; k<n; ++k){
      for (int i=0; i<n; ++i){
         for (int j=0; j<n; ++j){
            f1[i][j]=min(f1[i][j], f1[i][k]+f1[k][j]);
            f2[i][j]=min(f2[i][j], f2[i][k]+f2[k][j]);
         }
      }
   }
   auto get_dist=[&](int id, int x, int y) -> int {
      if (!id) return f2[x][y];
      return min(inf, f2[x][a[u[id-1]]]+f2[b[u[id-1]]][y]);
   };
   for (int i=0; i<q; ++i){
      for (int j=0; j<=_k; ++j) if (get_dist(j, s[i], t[i])<inf) mask[i]|=1<<j;
   }
   vector<pair<int, int>> order;
   for (int i=0; i<=_k; ++i){
      for (int j=i+1; j<=_k; ++j){
         order.emplace_back(i, j);
      }
   }
   shuffle(order.begin(), order.end(), rng);
   if (_k==5){
      order={
         {0, 1},
         {2, 3},
         {4, 5},
         {0, 2},
         {0, 3},
         {0, 4},
         {0, 5},
         {1, 2},
         {1, 3},
         {1, 4},
         {1, 5},
         {2, 4},
         {2, 5},
         {3, 4},
         {3, 5},
      };
   }
   for (auto &tmp:order){
      int i=tmp.first, j=tmp.second;
      vector<pair<int, int>> v;
      for (int k=0; k<q; ++k){
         if ((mask[k]>>i&1) && (mask[k]>>j&1)){
            v.emplace_back(get_dist(i, s[k], t[k])-get_dist(j, s[k], t[k]), k);
         }
      }
      sort(v.begin(), v.end());
      if (v.empty()) continue;
      int id=0;
      int diff=(c[u[j-1]])-(i?c[u[i-1]]:0);
      while (id!=v.size() && v[id].first<=diff) ++id;
      for (int t=0; t<id; ++t) mask[v[t].second]^=1<<j;
      for (int t=id; t<(int)v.size(); ++t) mask[v[t].second]^=1<<i;
      int lg=32-__builtin_clz(v.size());
      for (int l=0; l<lg; ++l) Tap(id>>l&1);
   }
}

Bruno

#include "Brunolib.h"

#include<bits/stdc++.h>

using namespace std;

#define int long long

static const int N=310;
static const int inf=0x3f3f3f3f3f3f3f3f;
static int id[6][6];
static int f[N][N], tr[N][N];
static int mask[60];

static mt19937 rng(69420);

void Bruno(int32_t n, int32_t m, int32_t a[], int32_t b[], int c[], int32_t q, int32_t s[], int32_t t[], int32_t _k, int32_t u[], int32_t _l, int32_t x[]) {
   int cur=0;
   memset(f, 0x3f, sizeof f);
   for (int i=0; i<m; ++i) if (c[i]!=-1){
      f[a[i]][b[i]]=c[i];
      tr[a[i]][b[i]]=i;
   }
   for (int i=0; i<n; ++i) f[i][i]=0;
   for (int k=0; k<n; ++k){
      for (int i=0; i<n; ++i){
         for (int j=0; j<n; ++j){
            if (f[i][j]>f[i][k]+f[k][j]){
               f[i][j]=f[i][k]+f[k][j];
               tr[i][j]=tr[i][k];
            }
         }
      }
   }
   auto get_dist=[&](int id, int x, int y) -> int {
      if (!id) return f[x][y];
      return min(inf, f[x][a[u[id-1]]]+f[b[u[id-1]]][y]);
   };
   auto get_path=[&](int x, int y) -> vector<int> {
      vector<int> ans;
      while (x!=y){
         ans.push_back(tr[x][y]);
         x=b[tr[x][y]];
      }
      return ans;
   };
   for (int i=0; i<q; ++i){
      for (int j=0; j<=_k; ++j) if (get_dist(j, s[i], t[i])<inf) mask[i]|=1<<j;
   }
   vector<pair<int, int>> order;
   for (int i=0; i<=_k; ++i){
      for (int j=i+1; j<=_k; ++j){
         order.emplace_back(i, j);
      }
   }
   shuffle(order.begin(), order.end(), rng);
   if (_k==5){
      order={
         {0, 1},
         {2, 3},
         {4, 5},
         {0, 2},
         {0, 3},
         {0, 4},
         {0, 5},
         {1, 2},
         {1, 3},
         {1, 4},
         {1, 5},
         {2, 4},
         {2, 5},
         {3, 4},
         {3, 5},
      };
   }
   for (auto &tmp:order){
      int i=tmp.first, j=tmp.second;
      vector<pair<int, int>> v;
      for (int k=0; k<q; ++k){
         if ((mask[k]>>i&1) && (mask[k]>>j&1)){
            v.emplace_back(get_dist(i, s[k], t[k])-get_dist(j, s[k], t[k]), k);
         }
      }
      sort(v.begin(), v.end());
      if (v.empty()) continue;
      int lg=32-__builtin_clz(v.size());
      for (int l=0; l<lg; ++l) id[i][j]|=x[cur++]<<l;
      for (int l=0; l<id[i][j]; ++l) mask[v[l].second]^=1<<j;
      for (int l=id[i][j]; l<(int)v.size(); ++l) mask[v[l].second]^=1<<i;
   }
   for (int i=0; i<q; ++i){
      vector<int> ans;
      if (mask[i]&1){
         ans=get_path(s[i], t[i]);
      }else{
         int best=__builtin_ctz(mask[i])-1;
         ans=get_path(s[i], a[u[0]]);
         auto tmp=get_path(b[u[best]], t[i]);
         ans.push_back(u[best]);
         ans.insert(ans.end(), tmp.begin(), tmp.end());
      }
      for (int j:ans) Answer(j);
      Answer(-1);
   }
}

Compilation message (stderr)

Anna.cpp: In function 'void Anna(int32_t, int32_t, int32_t*, int32_t*, long long int*, int32_t, int32_t*, int32_t*, int32_t, int32_t*)':
Anna.cpp:80:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |       while (id!=v.size() && v[id].first<=diff) ++id;
      |              ~~^~~~~~~~~~

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