#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<vector<int> > adj(501);
/// levo, desno, dali sme kaj levio element ili desnio, clockwise
bool visited[501][501][2];
int dp[501][501][2];
bool mat[501][501];
int f(int l,int r,int poz)
{
bool t = (l==poz);
if (visited[l][r][t]) return dp[l][r][t];
int odg = 0;
for (int sosed = l+1;sosed!=r;sosed++)
{
if (sosed>n) sosed = 1;
if (r == sosed) break;
if (l<r)
{
if ((l<sosed && sosed<r)==false) break;
}
if (r<l)
{
if ((l<sosed && sosed<r)==true) break;
}
if (mat[poz][sosed])
{
odg = max(f(l,sosed,sosed)+1,odg);
odg = max(f(sosed,r,sosed)+1,odg);
}
}
visited[l][r][t] = true;
dp[l][r][t] = odg;
//if (l==7 && r==2 && t) cout<< "depeto vika "<<odg<<endl;
return odg;
}
bool dolgvisited1[501][501];
int dolgdp1[501][501];
bool dolgvisited2[501][501];
int dolgdp2[501][501];
bool poseteno[501];
int kolku[501];
int pocetok, kraj;
int f1(int poz)
{
if (poz == kraj) return 0;
if (poseteno[poz]) return kolku[poz];
int sosed = poz+1;
int d = -10000;
while(true)
{
if (sosed>n) sosed = 1;
if (sosed==kraj)
{
if (mat[poz][sosed]) d = max(d,1);
break;
}
if (mat[poz][sosed]) d = max(d,f1(sosed)+1);
sosed++;
}
poseteno[poz] = true;
kolku[poz] = d;
return d;
}
int f2(int poz)
{
if (poz == kraj) return 0;
if (poseteno[poz]) return kolku[poz];
int sosed = poz-1;
int d = -10000;
while(true)
{
if (sosed==0) sosed = n;
if (sosed==kraj)
{
if(mat[poz][sosed]) d = max(d,1);
break;
}
if (mat[poz][sosed]) d = max(d,f2(sosed)+1);
sosed--;
}
poseteno[poz] = true;
kolku[poz] = d;
return d;
}
void sredi_intervali()
{
for (pocetok = 1;pocetok<=n;pocetok++)
for (kraj=1;kraj<=n;kraj++)
{
memset(poseteno,0,sizeof(poseteno));
dolgdp1[pocetok][kraj] = f1(pocetok);
//cout<<"od "<<pocetok<< " do "<<kraj<<" - "<<dolgdp1[pocetok][kraj]<<endl;
}
for (pocetok = 1;pocetok<=n;pocetok++)
for (kraj=1;kraj<=n;kraj++)
{
memset(poseteno,0,sizeof(poseteno));
dolgdp2[pocetok][kraj] = f2(pocetok);
}
}
int odg = 0, p = 0;
void presmetaj(int A,int B,int C,int D,bool eden)
{
//cout<<"ulava za "<<A<<" "<<B<<" "<<C<< " "<<D<<" eden="<<eden<<endl;
int x = 0;
if (eden)
{
x= 1 + dolgdp1[B][C]+ 1;
}
else
{
x = 1 + dolgdp2[B][C] + 1;
}
int y = max(dp[D][A][true], dp[D][B][true]);
x += y;
//cout<< A<<" "<<B<<" "<<C<<" "<<D<<"\n1+"<<x-y-1-1<<"+1+"<<y<<endl<<"x="<<x<<endl;
if (x>odg)
{
//cout<<"ulava\n";
odg = x;
p = A;
}
}
int main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
int a;
while(true)
{
cin>>a;
if (a==0) break;
//adj[i].push_back(a);
mat[i][a] = true;
}
}
for (int i=1;i<=n;i++)
{
int x = f(i,i,i);
if (x>odg)
{
odg = x;
p = i;
}
//cout<< "za i="<<i<< " odg = "<<x<<endl;
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
f(i,j,i);
f(i,j,j);
}
//cout<<odg<<endl<<p<<endl;
//return 0;
sredi_intervali();
for (int B=1;B<=n;B++)
{
int A = B+1;
if (A == n+1) A = 1;
for (int C=B+1;C!=B;C++)
{
if (C == n+1) C = 1;
if (C==B) break;
if (A==C) {
while (A!=B)
{
A++;
if (A==n+1) A = 1;
if (A==B) break;
if (mat[A][B]) break;
}
}
if (A==B) break;
for (int D = A+1; D!=B; D++)
{
if (D==n+1) D = 1;
if (D==B) break;
if (mat[A][B] && mat[C][D])
presmetaj(A,B,C,D,1);
}
}
A = B-1;
if (A==0) A = n;
for (int C=B-1;C!=B;C--)
{
if (C == 0) C = n;
if (C==B) break;
if (A==C) {
while (A!=B)
{
A--;
if (A==0) A = n;
if (A==B) break;
if (mat[A][B]) break;
}
}
if (A==B) break;
for (int D = A-1; D!=B; D--)
{
if (D==0) D = n;
if (D==B) break;
if (mat[A][B] && mat[C][D])
presmetaj(A,B,C,D,0);
}
}
}
cout<<odg<<endl<<p;
return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
4 1
3 0
0
4 0
2 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 5 |
Incorrect |
6 ms |
860 KB |
Output isn't correct |
| 6 |
Incorrect |
9 ms |
1032 KB |
Output isn't correct |
| 7 |
Incorrect |
24 ms |
1060 KB |
Output isn't correct |
| 8 |
Incorrect |
21 ms |
1116 KB |
Output isn't correct |
| 9 |
Incorrect |
60 ms |
1080 KB |
Output isn't correct |
| 10 |
Incorrect |
81 ms |
1368 KB |
Output isn't correct |
| 11 |
Incorrect |
97 ms |
1296 KB |
Output isn't correct |
| 12 |
Incorrect |
912 ms |
2224 KB |
Output isn't correct |
| 13 |
Execution timed out |
3050 ms |
2896 KB |
Time limit exceeded |
| 14 |
Execution timed out |
3087 ms |
3060 KB |
Time limit exceeded |
| 15 |
Execution timed out |
3062 ms |
3524 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3036 ms |
3276 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3027 ms |
3496 KB |
Time limit exceeded |
| 18 |
Execution timed out |
3058 ms |
3412 KB |
Time limit exceeded |
| 19 |
Execution timed out |
3063 ms |
3308 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3020 ms |
3336 KB |
Time limit exceeded |
