Contest Duration: ~ (local time) (240 minutes)

Submission #4545413

Source Code Expand

Copy
```#include <bits/stdc++.h>
#define N 1000000007
#define border 450
using namespace std;

long long n, q;
vector<vector<long long>> a;
vector<vector<vector<long long>>> memo;
map<pair<long long, long long>, long long> mp;

void setmemo();
long long solve(long long x, long long y);

int main() {
cin >> n;
a.resize(n);
for(int i = 0; i < n; ++i) {
long long k;
cin >> k;
a[i].resize(k);
for(int j = 0; j < k; ++j) cin >> a[i][j];
}
setmemo();
cin >> q;
for(int i = 0; i < q; ++i) {
long long x, y;
cin >> x >> y;
if(a[x].size() > a[y].size())
swap(x, y);
else if(a[x].size() == a[y].size() && x > y)
swap(x, y);
cout << solve(x, y) << endl;
}
return 0;
}

void setmemo() {
memo.resize(n);
for(int i = 0; i < n; ++i) {
memo[i].resize(min((int)a[i].size(), border));
int nowsize = memo[i].size();
for(int j = 0; j < nowsize; ++j) {
memo[i][j].resize(j + 1);
for(int k = 0; k < a[i].size(); ++k) {
memo[i][j][k % (j + 1)] += a[i][k];
memo[i][j][k % (j + 1)] %= N;
}
}
}
}

long long solve(long long x, long long y) {
if(mp.find({x, y}) != mp.end()) return mp[{x, y}];
long long ans = 0, nowsize = a[x].size();
if(nowsize >= border) {
nowsize = a[y].size();
for(long long i = 0; i < nowsize; ++i) {
ans += a[x][i % a[x].size()] * a[y][i] % N;
ans %= N;
}
return mp[{x, y}] = ans;
}
for(int i = 0; i < nowsize; ++i) {
ans += a[x][i] * memo[y][nowsize - 1][i] % N;
ans %= N;
}
return mp[{x, y}] = ans;
}
```

#### Submission Info

Submission Time 2019-03-11 01:53:29+0900 H - Doki Doki Programming Clubs! m_tsubasa C++14 (GCC 5.4.1) 200 1635 Byte AC 1367 ms 281088 KB

#### Test Cases

Set Name Score / Max Score Test Cases
All 200 / 200 0-sample-1, 0-sample-2, 0-sample1, 0-sample2, 1-random-large-0, 1-random-large-1, 1-random-large-2, 1-random-large-3, 1-random-large-4, 1-random-large-5, 1-random-large-6, 1-random-large-7, 1-random-large-8, 1-random-large-9, 2-challenge-0, 2-challenge-1, 2-challenge-2, 2-challenge-3, 2-challenge-4, 2-challenge-5, 2-challenge-6, 2-challenge-7, 2-challenge-8, 2-challenge-9, 3-challenge2-0, 3-challenge2-1, 3-challenge2-2, 3-challenge2-3, 3-challenge2-4, 3-challenge2-5, 3-challenge2-6, 3-challenge2-7, 3-challenge2-8, 3-challenge2-9, 4-maximum-0, 4-maximum-1, 5-increase-0, 5-increase-1, 6-increase2-0, 6-increase2-1, 7-nomemo-0, 7-nomemo-1
Case Name Status Exec Time Memory
0-sample-1 1 ms 256 KB
0-sample-2 1 ms 256 KB
0-sample1 1 ms 256 KB
0-sample2 1 ms 256 KB
1-random-large-0 986 ms 32128 KB
1-random-large-1 1037 ms 25856 KB
1-random-large-2 846 ms 45184 KB
1-random-large-3 1016 ms 28032 KB
1-random-large-4 1037 ms 24960 KB
1-random-large-5 913 ms 40576 KB
1-random-large-6 1024 ms 28800 KB
1-random-large-7 1001 ms 28672 KB
1-random-large-8 1031 ms 28672 KB
1-random-large-9 948 ms 35584 KB
2-challenge-0 815 ms 25856 KB
2-challenge-1 761 ms 14208 KB
2-challenge-2 737 ms 13184 KB
2-challenge-3 742 ms 13952 KB
2-challenge-4 749 ms 15232 KB
2-challenge-5 729 ms 16640 KB
2-challenge-6 750 ms 19200 KB
2-challenge-7 741 ms 20992 KB
2-challenge-8 744 ms 21760 KB
2-challenge-9 744 ms 22528 KB
3-challenge2-0 809 ms 24064 KB
3-challenge2-1 792 ms 14336 KB
3-challenge2-2 763 ms 13440 KB
3-challenge2-3 762 ms 14336 KB
3-challenge2-4 737 ms 15616 KB
3-challenge2-5 742 ms 17024 KB
3-challenge2-6 737 ms 19584 KB
3-challenge2-7 741 ms 21376 KB
3-challenge2-8 748 ms 22144 KB
3-challenge2-9 748 ms 22912 KB
4-maximum-0 817 ms 42752 KB
4-maximum-1 797 ms 42752 KB
5-increase-0 1361 ms 281088 KB
5-increase-1 1367 ms 281088 KB
6-increase2-0 1106 ms 129792 KB
6-increase2-1 1118 ms 129792 KB
7-nomemo-0 871 ms 5376 KB
7-nomemo-1 872 ms 5376 KB