#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector
const int MAX_N = 500;
int dp[MAX_N][MAX_N][2] = {0}, dp2[MAX_N][MAX_N][2] = {0};
int nxt[MAX_N][2];
int mx[MAX_N][MAX_N][2] = {0};
bool adj[MAX_N][MAX_N] = {false};
// ccw: 0; cw: 1
// dp[i][j][ccw/cw]: start at i, end at or past j, in the ccw/cw direction
// dp2[i][j][ccw/cw]: start at i, end at j, moving only in the ccw/cw direction
int main() {
ios::sync_with_stdio(false); cin.tie(0);
int n, t; cin >> n >> t;
//n=500;
F0R(i,n) {
int x; cin >> x;
//for (int x=1;x<=n;x++) {if (x==i+1) {continue;}adj[i][x-1] = true;}
while (x!=0) {
adj[i][--x] = true;
dp[i][x][0] = dp2[i][x][0] = dp[i][x][1] = dp2[i][x][1] = 1;
cin >> x;
}
}
F0R(i,n) {
nxt[i][0] = (i+1)%n;
nxt[i][1] = (i-1+n)%n;
}
FOR(len,2,n) {
F0R(i,n) {
int k = (i+len)%n;
// for ccw, transition from dp[start][mid][0], dp[mid][start][1]
// for cw, transition from dp[start][mid][1], dp[mid][start][0]
F0R(st,2) {
for (int j=k;j!=i;j=nxt[j][!st]) { // from start to end in the direction
if (adj[i][j]) {
if (dp[j][k][st]) {
chmax(dp[i][k][st],dp[j][k][st]+1);
}
if (dp2[j][k][st]) {
chmax(dp2[i][k][st],dp2[j][k][st]+1);
}
//if (i==37 && k==39 && st==0) {cout << j << ' ' << k << ' '<<dp2[j][k][st]<<'\n';}
}
if (adj[i][k] && dp[k][j][!st]) {
chmax(dp[i][k][st],dp[k][j][!st]+1);
}
}
k = (i-len+n)%n;
}
}
}
// dp updates such that dp[i][j][cw/ccw] = start at i, finish >=j (for ccw), <=j (for cw)
// doit
F0R(i,n) {
F0R(st,2) {
for (int j=nxt[i][st];j!=i;j=nxt[j][st]) {
chmax(dp[i][j][st],dp[i][nxt[j][!st]][st]);
}
}
}
int ans_zero = 0, start_zero = 0, ans_one = 0, start_one = 0;
F0R(stop,n) {
//if (stop!=106) {continue;}
F0R(st,2) {
// case k=0
int cand_zero = dp[stop][nxt[stop][!st]][st];
if (cand_zero>ans_zero) {
ans_zero = cand_zero;
start_zero = stop+1;
}
for (int start=nxt[stop][st];start!=stop;start=nxt[start][st]) { // make one full circle
// case k=1: update radj and answer
int cand_one = 0;
for (int cand=nxt[stop][!st];cand!=start;cand=nxt[cand][!st]) {
if (adj[start][stop] && mx[stop][cand][st]) {
int aft = max(dp[cand][nxt[start][st]][!st],dp[cand][nxt[stop][!st]][st]);
chmax(cand_one,1+mx[stop][cand][st]+aft);
//if (mx[stop][cand][st]+aft+1==263 && start==108) {cout<<cand<<'\n';}
}
if (adj[start][cand] && dp2[stop][start][st]) {
chmax(mx[stop][cand][st],dp2[stop][start][st]+1);
//if (dp2[stop][start][st]==2 && stop==35 && cand==1 && st==0) {
//cout << start << '\n';
//}
}
}
/*if (cand_one==263 && start==108) {
// cand:1 st: 0 stop: 35 mx: 3 turn: 39 start: 0
// 0 -> 35 -> 39 -> 1 -> ??
// st: 106 start: 108 stop: 106 cand: 109
cout << stop << ' ' << st << ' ' << '\n';
cout << stop << " " << mx[stop][109][st] << '\n';
}*/
if (cand_one>ans_one) {
ans_one = cand_one;
start_one = start+1;
}
}
}
}
if (ans_zero>ans_one || t==0) {
cout << ans_zero << '\n' << start_zero << '\n';
} else {
cout << ans_one << '\n' << start_one << '\n';
}
/*
k=0 do dp because available forms a range, define by dp[start][end][cw/ccw]
currently at end
k=1
first line, then work on one half; range must be an end segment of the original
only then can you move to the other half and do stuff there
so it must constantly reduce the same side of the range
meaning that all cities must be in a cw/ccw arc
dp2[start][end][cw/ccw] max cities from start to end in a cw/ccw arc
then fix all start lines
and then fix all midpoints
and then fix all
thats n^4
fix first endpoint
do recursive min calculation to this endpoint so n^2 total calcs
while moving second endpoint
so when moving second endpoint update all connected ones
then fix the next node, you already have the min, take min dist to endpoints
blah blah blah
so n^3 total
side case n=1
whole alg:
do k=0 dp
check which endpoint currently at, transition from all reachable ports if
they are in the range, and then there are two ranges to transition to
do an adjacency matrix and basic iteration over mid
ranges becomes [start,mid] or [mid,end]
pull from them, +1 for this range
dp2: only allowed to pull from [mid,end]
base case: dp[0][0][0] = dp[0][0][1] = 1;
calc initial answer:
fix all start/end points and just do max for two side dps
k=1:
initialize a min table for each index
fix endpoints in ccw order
first remove the endpoint from the table, then access all radj to upd min
and then fix midpoint and take best answer, by adding its min value
with the answer to either endpoint for dp1
*/
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
