#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];
//cout<< "l="<<l<<" r="<<r<<" poz="<<poz<<endl;
//system("pause");
//cout<<endl;
int odg = 0;
for (int sosed = l+1;sosed!=r;sosed++)
{
if (sosed>n) sosed = 1;
if (r == sosed) break;
if (mat[poz][sosed])
{
odg = max(f(l,sosed,sosed)+1,odg);
odg = max(f(sosed,r,sosed)+1,odg);
}
else{
odg = max(odg,f(l,sosed,l));
}
}
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)
{
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;
if (x>odg)
{
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;
}
}
if (m==0 || true)
{
cout<<odg<<endl<<p<<endl;
return 0;
}
sredi_intervali();
for (int B=1;B<=n;B++)
{
//cout<<"ulava u B="<<B<<endl;
int C = B+1;
if (C>n) C=1;
while(C!=B)
{
int A = C+1;
if (A>n) A=1;
while(A!=B)
{
if (mat[A][B]==true) break;
A++;
if (A>n) A=1;
}
if (A!=B)
{
int D = A+1;
if (D>n) D=1;
while(D!=B)
{
if (mat[C][D]==true)
{
presmetaj(A,B,C,D,true);
}
D++;
if (D>n) D=1;
}
}
C++;
if (C>n) C=1;
}
/// sea counter klakwajs
C = B-1;
if (C==0) C=n;
while(C!=B)
{
int A = C-1;
if (A==0) A=n;
while(A!=B)
{
if (mat[A][B]==true) break;
A--;
if (A==0) A=n;
}
if (A!=B)
{
int D = A-1;
if (D==0) D=n;
while(D!=B)
{
if (mat[C][D]==true)
{
presmetaj(A,B,C,D,false);
}
D--;
if (D==0) D=n;
}
}
C--;
if (C==0) C=n;
}
}
cout<<odg<<endl<<p<<endl;
return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 4 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
| 5 |
Incorrect |
1 ms |
716 KB |
Output isn't correct |
| 6 |
Correct |
2 ms |
604 KB |
Output is correct |
| 7 |
Correct |
3 ms |
604 KB |
Output is correct |
| 8 |
Incorrect |
3 ms |
856 KB |
Output isn't correct |
| 9 |
Incorrect |
5 ms |
968 KB |
Output isn't correct |
| 10 |
Correct |
8 ms |
860 KB |
Output is correct |
| 11 |
Correct |
7 ms |
856 KB |
Output is correct |
| 12 |
Incorrect |
39 ms |
1368 KB |
Output isn't correct |
| 13 |
Incorrect |
110 ms |
2168 KB |
Output isn't correct |
| 14 |
Incorrect |
247 ms |
2644 KB |
Output isn't correct |
| 15 |
Incorrect |
592 ms |
3020 KB |
Output isn't correct |
| 16 |
Incorrect |
623 ms |
3156 KB |
Output isn't correct |
| 17 |
Incorrect |
606 ms |
3156 KB |
Output isn't correct |
| 18 |
Incorrect |
438 ms |
3156 KB |
Output isn't correct |
| 19 |
Incorrect |
701 ms |
3156 KB |
Output isn't correct |
| 20 |
Incorrect |
645 ms |
3156 KB |
Output isn't correct |
