Submission #971157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
971157	2024-04-28T05:13:53 Z	huutuan	한자 끝말잇기 (JOI14_kanji)	C++14	100 / 100	139 ms	19060 KB

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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	10160 KB	Output is correct - L = 25
2	Correct	64 ms	10148 KB	Output is correct - L = 24
3	Correct	61 ms	9948 KB	Output is correct - L = 15
4	Correct	61 ms	9944 KB	Output is correct - L = 20
5	Correct	62 ms	9952 KB	Output is correct - L = 27
6	Correct	61 ms	10644 KB	Output is correct - L = 19
7	Correct	60 ms	10008 KB	Output is correct - L = 18
8	Correct	63 ms	9960 KB	Output is correct - L = 20
9	Correct	68 ms	10244 KB	Output is correct - L = 20
10	Correct	68 ms	10440 KB	Output is correct - L = 20
11	Correct	61 ms	10308 KB	Output is correct - L = 4
12	Correct	132 ms	18560 KB	Output is correct - L = 20
13	Correct	61 ms	10136 KB	Output is correct - L = 20
14	Correct	60 ms	10008 KB	Output is correct - L = 0

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	62 ms	10456 KB	Output is correct - L = 42
2	Correct	66 ms	10472 KB	Output is correct - L = 57
3	Correct	61 ms	10552 KB	Output is correct - L = 34
4	Correct	61 ms	10548 KB	Output is correct - L = 39
5	Correct	64 ms	10252 KB	Output is correct - L = 54
6	Correct	62 ms	10576 KB	Output is correct - L = 58
7	Correct	64 ms	10548 KB	Output is correct - L = 30
8	Correct	64 ms	10632 KB	Output is correct - L = 41
9	Correct	61 ms	10688 KB	Output is correct - L = 64
10	Correct	64 ms	10480 KB	Output is correct - L = 64
11	Correct	62 ms	10560 KB	Output is correct - L = 64
12	Correct	62 ms	10648 KB	Output is correct - L = 0
13	Correct	132 ms	19060 KB	Output is correct - L = 30
14	Correct	72 ms	10756 KB	Output is correct - L = 47
15	Correct	62 ms	10556 KB	Output is correct - L = 31
16	Correct	66 ms	10332 KB	Output is correct - L = 30
17	Correct	69 ms	10628 KB	Output is correct - L = 33
18	Correct	76 ms	11212 KB	Output is correct - L = 40
19	Correct	63 ms	9968 KB	Output is correct - L = 29
20	Correct	72 ms	11524 KB	Output is correct - L = 35
21	Correct	74 ms	11428 KB	Output is correct - L = 35
22	Correct	62 ms	10480 KB	Output is correct - L = 64
23	Correct	61 ms	10644 KB	Output is correct - L = 63
24	Correct	61 ms	10548 KB	Output is correct - L = 63

Subtask #3

8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	10456 KB	Output is correct - L = 42
2	Correct	61 ms	10456 KB	Output is correct - L = 57
3	Correct	61 ms	10460 KB	Output is correct - L = 34
4	Correct	63 ms	10452 KB	Output is correct - L = 39
5	Correct	64 ms	10020 KB	Output is correct - L = 54
6	Correct	62 ms	10580 KB	Output is correct - L = 58
7	Correct	62 ms	10672 KB	Output is correct - L = 30
8	Correct	63 ms	10632 KB	Output is correct - L = 41
9	Correct	61 ms	10596 KB	Output is correct - L = 64
10	Correct	62 ms	10548 KB	Output is correct - L = 64
11	Correct	61 ms	10480 KB	Output is correct - L = 64
12	Correct	69 ms	10564 KB	Output is correct - L = 0
13	Correct	139 ms	19044 KB	Output is correct - L = 30
14	Correct	62 ms	10464 KB	Output is correct - L = 47
15	Correct	61 ms	10640 KB	Output is correct - L = 31
16	Correct	66 ms	10640 KB	Output is correct - L = 30
17	Correct	68 ms	10696 KB	Output is correct - L = 33
18	Correct	73 ms	11152 KB	Output is correct - L = 40
19	Correct	62 ms	9956 KB	Output is correct - L = 29
20	Correct	68 ms	11444 KB	Output is correct - L = 35
21	Correct	73 ms	11416 KB	Output is correct - L = 35
22	Correct	62 ms	10484 KB	Output is correct - L = 64
23	Correct	61 ms	10540 KB	Output is correct - L = 63
24	Correct	64 ms	10580 KB	Output is correct - L = 63

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	10592 KB	Output is correct - L = 42
2	Correct	62 ms	10480 KB	Output is correct - L = 57
3	Correct	64 ms	10520 KB	Output is correct - L = 34
4	Correct	61 ms	10556 KB	Output is correct - L = 39
5	Correct	61 ms	9964 KB	Output is correct - L = 54
6	Correct	64 ms	10540 KB	Output is correct - L = 58
7	Correct	61 ms	10588 KB	Output is correct - L = 30
8	Correct	62 ms	10724 KB	Output is correct - L = 41
9	Correct	63 ms	10484 KB	Output is correct - L = 64
10	Correct	65 ms	10880 KB	Output is correct - L = 64
11	Correct	61 ms	10476 KB	Output is correct - L = 64
12	Correct	63 ms	10564 KB	Output is correct - L = 0
13	Correct	131 ms	19000 KB	Output is correct - L = 30
14	Correct	63 ms	10468 KB	Output is correct - L = 47
15	Correct	64 ms	10724 KB	Output is correct - L = 31
16	Correct	67 ms	10600 KB	Output is correct - L = 30
17	Correct	68 ms	10628 KB	Output is correct - L = 33
18	Correct	72 ms	11072 KB	Output is correct - L = 40
19	Correct	66 ms	10208 KB	Output is correct - L = 29
20	Correct	68 ms	11508 KB	Output is correct - L = 35
21	Correct	78 ms	11312 KB	Output is correct - L = 35
22	Correct	61 ms	10544 KB	Output is correct - L = 64
23	Correct	61 ms	10476 KB	Output is correct - L = 63
24	Correct	63 ms	10584 KB	Output is correct - L = 63

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	10524 KB	Output is correct - L = 42
2	Correct	65 ms	10992 KB	Output is correct - L = 57
3	Correct	63 ms	10520 KB	Output is correct - L = 34
4	Correct	60 ms	10536 KB	Output is correct - L = 39
5	Correct	61 ms	10172 KB	Output is correct - L = 54
6	Correct	63 ms	10712 KB	Output is correct - L = 58
7	Correct	61 ms	10628 KB	Output is correct - L = 30
8	Correct	63 ms	10580 KB	Output is correct - L = 41
9	Correct	61 ms	10604 KB	Output is correct - L = 64
10	Correct	60 ms	10548 KB	Output is correct - L = 64
11	Correct	69 ms	10592 KB	Output is correct - L = 64
12	Correct	62 ms	10472 KB	Output is correct - L = 0
13	Correct	128 ms	18988 KB	Output is correct - L = 30
14	Correct	63 ms	10472 KB	Output is correct - L = 47
15	Correct	63 ms	10424 KB	Output is correct - L = 31
16	Correct	66 ms	10528 KB	Output is correct - L = 30
17	Correct	71 ms	10696 KB	Output is correct - L = 33
18	Correct	71 ms	11128 KB	Output is correct - L = 40
19	Correct	62 ms	9956 KB	Output is correct - L = 29
20	Correct	71 ms	11440 KB	Output is correct - L = 35
21	Correct	73 ms	11432 KB	Output is correct - L = 35
22	Correct	60 ms	10480 KB	Output is correct - L = 64
23	Correct	61 ms	10592 KB	Output is correct - L = 63
24	Correct	61 ms	10572 KB	Output is correct - L = 63