Task: | Ruudukko |
Sender: | Lordoa |
Submission time: | 2022-11-13 18:48:42 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 0 |
group | verdict | score |
---|---|---|
#1 | WRONG ANSWER | 0 |
#2 | WRONG ANSWER | 0 |
#3 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#2 | WRONG ANSWER | 0.00 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.00 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 2, 3 | details |
#5 | WRONG ANSWER | 0.01 s | 2, 3 | details |
#6 | WRONG ANSWER | 0.02 s | 2, 3 | details |
#7 | WRONG ANSWER | 0.09 s | 3 | details |
#8 | TIME LIMIT EXCEEDED | -- | 3 | details |
#9 | TIME LIMIT EXCEEDED | -- | 3 | details |
Code
#include <iostream>int n;int visited = 0;int sum = 0;int arr[1001][1001];int gps[1001][1001]={0};int gps2[3][1001];int route(int x, int y){if (gps[x][y]!=0)return gps[x][y];int gpsdie = (gps2[0][y]<gps2[1][x]) ? gps2[0][y] : gps2[1][x];if (arr[x][y]==gpsdie){gps[x][y] = 1;visited++;sum++;return 1;}int routes = 1;for (int i=0;i<n;i++){if (y!=i){if (arr[x][i]<arr[x][y])routes += route(x,i);//if (routes>1000000007)routes %= 1000000007;}if (x!=i){if (arr[i][y]<arr[x][y])routes += route(i,y);//if (routes>1000000007)routes %= 1000000007;}}gps[x][y] = routes;visited++;sum += routes;if (sum>=1000000007)sum %= 1000000007;return routes;}int main(){std::cin.sync_with_stdio(false);std::cin >> n;for (int i=0;i<n;i++){for (int j=0;j<n;j++){std::cin >> arr[i][j];}}int xd = n*n;int small = 1000001;for (int i=0;i<n;i++){for (int j=0;j<n;j++){if (arr[j][i]<small)small = arr[j][i];}for (int j=0;j<n;j++){gps2[j][i] = small;}small = 1000001;for (int j=0;j<n;j++){if (arr[i][j]<small)small = arr[i][j];}for (int j=0;j<n;j++){gps2[i][j] = small;}small = 1000001;}for (int i=0;i<n;i++){for (int j=0;j<n;j++){route(i,j);if (visited==xd)goto results;}}results:std::cout << sum << "\n";return 0;}
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 1 1 1 1 1 1 1 1 1 |
correct output |
---|
9 |
user output |
---|
9 |
Test 2
Group: 1, 2, 3
Verdict: WRONG ANSWER
input |
---|
3 1 2 3 6 5 4 7 8 9 |
correct output |
---|
135 |
user output |
---|
73 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
3 7 8 1 4 5 4 3 9 6 |
correct output |
---|
57 |
user output |
---|
57 |
Test 4
Group: 2, 3
Verdict: ACCEPTED
input |
---|
100 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
10000 |
user output |
---|
10000 |
Test 5
Group: 2, 3
Verdict: WRONG ANSWER
input |
---|
100 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
187458477 |
user output |
---|
192390445 |
Test 6
Group: 2, 3
Verdict: WRONG ANSWER
input |
---|
100 2995 8734 1018 2513 7971 5063 ... |
correct output |
---|
964692694 |
user output |
---|
390817079 |
Test 7
Group: 3
Verdict: WRONG ANSWER
input |
---|
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
correct output |
---|
1000000 |
user output |
---|
997012 |
Test 8
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1 2 3 4 5 6 7 8 9 10 11 12 13 ... |
correct output |
---|
229147081 |
user output |
---|
(empty) |
Test 9
Group: 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 520283 805991 492643 75254 527... |
correct output |
---|
951147313 |
user output |
---|
(empty) |