#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 500;
vector<vector<int>> a(MAXN, vector<int>(MAXN)), aa(MAXN, vector<int>(MAXN));
vector<vector<int>> md(MAXN, vector<int>(MAXN)), mdc(MAXN, vector<int>(MAXN));
vector<vector<int>> ed(MAXN, vector<int>(MAXN)), edc(MAXN, vector<int>(MAXN));
vector<vector<bool>> adj(MAXN, vector<bool>(MAXN));
vector<int> last(MAXN), b(MAXN), bb(MAXN);
int n, kk, max_val, maxi;
void inp() {
cin >> n >> kk;
for (int i = 0; i < n; i++) {
int x;
while (cin >> x && x > 0) {
adj[i][x-1] = true;
}
}
fill(b.begin(), b.end(), 0);
fill(bb.begin(), bb.end(), 0);
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
while (i != j) {
if (adj[i][j]) {
b[i]++;
a[i][b[i]] = j;
md[i][j] = 1;
mdc[i][j] = 1;
}
if (adj[j][i]) {
bb[i]++;
aa[i][bb[i]] = j;
}
j = (j + 1) % n;
}
}
}
void calc() {
for (int i = 0; i < n; i++) {
md[i][i] = mdc[i][i] = ed[i][i] = edc[i][i] = 0;
}
for (int t = 1; t < n; t++) {
for (int i = 0; i < n; i++) {
for (int j = 1; j <= b[i]; j++) {
int y = a[i][j];
int x = (i + t) % n;
int h = (y + n - i) % n;
if (h < t) {
if (md[y][x] > 0 && md[y][x] >= md[i][x])
md[i][x] = md[y][x] + 1;
if (ed[y][x] >= ed[i][x])
ed[i][x] = ed[y][x] + 1;
if (edc[y][i] >= ed[i][x])
ed[i][x] = edc[y][i] + 1;
}
x = (i + n - t) % n;
h = (i + n - y) % n;
if (h < t) {
if (mdc[y][x] > 0 && mdc[y][x] >= mdc[i][x])
mdc[i][x] = mdc[y][x] + 1;
if (edc[y][x] >= edc[i][x])
edc[i][x] = edc[y][x] + 1;
if (ed[y][i] >= edc[i][x])
edc[i][x] = ed[y][i] + 1;
}
}
}
}
max_val = 0;
for (int i = 0; i < n; i++) {
if (edc[i][i] > max_val) {
max_val = edc[i][i];
maxi = i;
}
if (ed[i][i] > max_val) {
max_val = ed[i][i];
maxi = i;
}
}
}
void opt() {
for (int i = 0; i < n; i++) {
// case 1: i y z x 为正 positive
for (int j = 2; j < n; j++) {
int x = (i + j) % n;
int k = 1;
while (k <= bb[x] && (aa[x][k] + n - i - 1) % n > j - 1) k++;
last[x] = (k <= bb[x]) ? aa[x][k] : -1;
}
for (int j = 2; j < n - 1; j++) {
if (adj[i][(i + j) % n]) {
int z = (i + j) % n;
for (int k = j + 1; k < n; k++) {
int x = (i + k) % n;
if (last[x] > -1 && (n + last[x] - i) % n < j && md[x][i] > 0) {
int tmp = 1 + md[x][i] + 1 + max(edc[z][last[x]], ed[z][x]);
if (tmp > max_val) {
max_val = tmp;
maxi = last[x];
}
}
}
}
}
// case 2: i y z x 为负 negative
for (int j = 1; j < n - 1; j++) {
int x = (i + j) % n;
int k = 1;
while (k <= bb[x] && (aa[x][k] + n - i) % n > j) k++;
last[x] = (k > 1) ? aa[x][k - 1] : -1;
}
for (int j = 2; j < n - 1; j++) {
if (adj[i][(i + j) % n]) {
int z = (i + j) % n;
for (int k = 1; k < j; k++) {
int x = (i + k) % n;
if (last[x] > -1 && (n + last[x] - i) % n > j && mdc[x][i] > 0) {
int tmp = 1 + mdc[x][i] + 1 + max(ed[z][last[x]], edc[z][x]);
if (tmp > max_val) {
max_val = tmp;
maxi = last[x];
}
}
}
}
}
}
}
int main() {
inp();
calc();
if (kk == 1) opt();
cout << max_val << endl;
cout << maxi + 1 << endl;
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
6488 KB |
Output isn't correct |
| 2 |
Correct |
4 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
4 ms |
6488 KB |
Output is correct |
| 4 |
Correct |
4 ms |
6488 KB |
Output is correct |
| 5 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 6 |
Correct |
5 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
6 ms |
6492 KB |
Output isn't correct |
| 8 |
Correct |
6 ms |
6492 KB |
Output is correct |
| 9 |
Incorrect |
7 ms |
6492 KB |
Output isn't correct |
| 10 |
Incorrect |
11 ms |
6492 KB |
Output isn't correct |
| 11 |
Incorrect |
9 ms |
6488 KB |
Output isn't correct |
| 12 |
Correct |
34 ms |
6492 KB |
Output is correct |
| 13 |
Correct |
54 ms |
6496 KB |
Output is correct |
| 14 |
Incorrect |
57 ms |
6504 KB |
Output isn't correct |
| 15 |
Correct |
276 ms |
6488 KB |
Output is correct |
| 16 |
Correct |
343 ms |
6488 KB |
Output is correct |
| 17 |
Correct |
277 ms |
6492 KB |
Output is correct |
| 18 |
Incorrect |
73 ms |
6488 KB |
Output isn't correct |
| 19 |
Correct |
408 ms |
6636 KB |
Output is correct |
| 20 |
Correct |
415 ms |
6492 KB |
Output is correct |
