#include <bits/stdc++.h>
// #pragma GCC optimize("O3, unroll-loops")
// #pragma GCC target("avx2")
// #define int long long
using namespace std;
#define _upgrade \
ios_base::sync_with_stdio(0); \
cin.tie(0); \
cout.tie(0);
#define LINE "---------------------\n"
#define ALL(A) A.begin(), A.end()
#define LLA(A) A.rbegin(), A.rend()
#define Q queue
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
using db = double;
using ld = long double;
using sint = short int;
using ll = long long;
using uint = unsigned int;
// PQ going up <int, VI, greater<int> >
using VI = vector<int>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
using VB = vector<bool>;
using VVB = vector<VB>;
using VVVB = vector<VVB>;
using VLL = vector<ll>;
using VVLL = vector<VLL>;
using PII = pair<int, int>;
using VPI = vector<PII>;
using VVPI = vector<VPI>;
using PLL = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int strToInt(string&a) {
stringstream x(a);
int b;
x >> b;
return b;
}
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
/*
| _
| __ _ | |
| | \| | ___ ___ | |_
| | |\ | |/ _ \/ __/| __|
| | | \ | __/\__ \| |_
| |_| \_|\___ /___/ \__|
| _ _ _
| (_) | | | |
| _ __ _ __ ___ __ _ _ __ __ _ _ __ ___ _ __ ___ _ ___ ___| |_| |_
| | '_ \| '__/ _ \ / _` | '__/ _` | '_ ` _ \| '_ ` _ \| / __/ __| __| __|
| | |_) | | | (_) | (_| | | | (_| | | | | | | | | | | | \__ \__ \ |_| |_
| | .__/|_| \___/ \__, |_| \__,_|_| |_| |_|_| |_| |_|_|___/___/\__|\__|
| | | __/ |
| |_| |___/ _
| _ (_)
| _ __ ___ __ _ ____ __ _ __ _| | __ _ _
| | '_ ` _ \ / _` |_ / _` |/ _` | |/ _` | |
| | | | | | | (_| / / (_| | (_| | | (_| | |
| |_| |_| |_|\__,_|____\__,_|\__,_|_|\__,_|_|
*/
const db PI = acos(-1.0); //M_PI;
const ll INFF = 4e18;
const int INF = 1.07e9;
const int MOD = 1e9 + 7;
const int MOD1 = 998244353; //7*19*2^23 +1;
const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int N = 500 + 5;
const int M = 2e5 + 5;
int nums[N];
int n, m, k, q, type;
string s;
vector <int> paths[N];
bool edge[N][N];
int dp[N][N][2];
bool mid (int l, int r, int m) {
if (l < r) return (l < m && m < r);
return (
(l < m && m < n) ||
(l > m && m < r)
);
}
int f (int a) {
return (a+1)%n;
}
void go () {
cin >> n >> type;
for (int i = 0, x; i < n; i++) {
while(cin >> x && x-- != 0) {
// paths[i].pb(x);
edge[i][x] = 1;
}
}
PII ans = {0, 1};
for (int d = 2; d < n; d++)
for (int l = 0, r = (l+d)%n; l < n ; l++, r=f(r)) {
for (int m = f(l); m != r; m=f(m)) {
chmax(ans, mp(dp[l][r][0], l));
chmax(ans, mp(dp[l][r][1], r));
if (edge[l][m] && mid(l, r, m)) {
chmax(dp[l][r][0], dp[l][m][1]+1);
chmax(dp[l][r][0], dp[m][r][0]+1);
}
if (edge[r][m] && mid(l, r, m)) {
chmax(dp[l][r][1], dp[l][m][1]+1);
chmax(dp[l][r][1], dp[m][r][0]+1);
}
}
if (l == n-1) break;
}
cout << ans.ff << '\n' << ans.ss << '\n';
}
signed main () {
#ifndef ONLINE_JUDGE
// freopen("0.in", "r", stdin);
// freopen("0.out", "w", stdout);
#endif
_upgrade
int T = 1;
while(T--) go();
return (0-0); //<3
}
/* stuff you should look for
* int overflow, array bounds
* special cases (n=1?)
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
468 KB |
Output is correct |
| 6 |
Incorrect |
2 ms |
596 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
596 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
708 KB |
Output isn't correct |
| 9 |
Incorrect |
6 ms |
748 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
796 KB |
Output isn't correct |
| 11 |
Incorrect |
8 ms |
724 KB |
Output isn't correct |
| 12 |
Incorrect |
36 ms |
1224 KB |
Output isn't correct |
| 13 |
Incorrect |
108 ms |
1664 KB |
Output isn't correct |
| 14 |
Incorrect |
205 ms |
2112 KB |
Output isn't correct |
| 15 |
Incorrect |
480 ms |
2552 KB |
Output isn't correct |
| 16 |
Incorrect |
585 ms |
2636 KB |
Output isn't correct |
| 17 |
Incorrect |
486 ms |
2548 KB |
Output isn't correct |
| 18 |
Incorrect |
359 ms |
2640 KB |
Output isn't correct |
| 19 |
Incorrect |
571 ms |
2552 KB |
Output isn't correct |
| 20 |
Incorrect |
582 ms |
2560 KB |
Output isn't correct |
