#include <bits/stdc++.h>
using namespace std;
int n,k;
const int MAX=501;
bool mat[MAX][MAX];
int vis[MAX][MAX][2];
int dp[MAX][MAX][2];
int f(int a, int b, int dir)
{
bool t=(dir==a);
// cout<<"a: "<<a+1<<" b: "<<b+1<<endl;
if(vis[a][b][t])return dp[a][b][t];
int res=0;
for(int i=a+1; i!=b; i++)
{
if(i==n)i=0;
if(i==b)break;
if (a<b)
{
if ((a<i && i<b)==false) break;
}
if (b<a)
{
if ((a<i && i<b)==true) break;
}
if(mat[dir][i])
{
res=max(res,f(a,i,i)+1);
res=max(res,f(i,b,i)+1);
}
}
vis[a][b][t]=true;
dp[a][b][t]=res;
return res;
}
int nalevo[MAX][MAX];
void ODBDOC(int start, int node, int cnt)
{
nalevo[start][node]=max(nalevo[start][node],cnt);
for(int i=node+1; i!=node; i++)
{
if(i==n)i=0;
if(i==node)break;
else if(i==start)break;
if(mat[node][i])ODBDOC(start,i,cnt+1);
}
}
int nadesno[MAX][MAX];
void kurAC(int start, int node, int cnt)
{
nadesno[start][node]=max(nadesno[start][node],cnt);
for(int i=node-1; i!=node; i--)
{
if(i<0)i=n-1;
if(i==node)break;
else if(i==start)break;
if(mat[node][i])kurAC(start,i,cnt+1);
}
}
bool preklopuvaat(int a, int b, int c, int d)
{
if(a>b)swap(a,b);
if(c>=a && c<=b)
{
if(d>=a && d<=b)return false;
return true;
}
if(d>=a && d<=b)
{
if(c>=a && c<=b)return false;
return true;
}
return false;
}
int main()
{
cin>>n>>k;
for(int i=0; i<n; i++)
{
int x;
while(cin>>x)
{
if(x==0)break;
x--;
mat[i][x]=true;
}
}
if(k==0)
{
int poz,res=0;
for(int i=0; i<n; i++)
{
int tmp=f(i,i,i);
if(tmp>res)
{
res=tmp;
poz=i;
}
}
cout<<res<<endl<<poz+1<<endl;
return 0;
}
for(int i=0; i<n; i++)
{
ODBDOC(i,i,0);
kurAC(i,i,0);
}
int mxx=0,poz;
for(int a=0; a<n; a++)
{
for(int b=0; b<n; b++)
{
if(a==b)continue;
for(int c=0; c<n; c++)
{
if(a==c || b==c)continue;
for(int d=0; d<n; d++)
{
if(d==a || d==b || d==c)continue;
if(!mat[a][b] || !mat[c][d])continue;
if(!preklopuvaat(a,b,c,d))continue;
int tmpres=2;
int X;
if((a<b && c>b && c>a)|| (a>b && b<c && c<a))///tri lepe pa levo
{
tmpres+=nalevo[b][c];
X=nalevo[b][c];
}
else ///tri lepe pa desno
{
tmpres+=nadesno[b][c];
X=nadesno[b][c];
}
if(X==0)continue;
int gore=f(b,d,d);
int dolu=f(d,a,d);
tmpres+=max(gore,dolu);
if(tmpres>mxx)
{
mxx=tmpres;
poz=a;
}
/*cout<<"A: "<<a+1<< " B: "<<b+1<<" C: "<<c+1<<" D: "<<d+1<<" RES:";
cout<<tmpres<<endl;
cout<<"OD B DO C:"<< X<<endl<<endl;
cout<<"gore: "<<gore<<" dolu: "<<dolu<<endl;*/
}
}
}
}
cout<<mxx<<endl<<poz+1<<endl;
return 0;
}
Compilation message
race.cpp: In function 'int main()':
race.cpp:156:26: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
156 | cout<<mxx<<endl<<poz+1<<endl;
| ^
race.cpp:104:30: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | cout<<res<<endl<<poz+1<<endl;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 4 |
Incorrect |
6 ms |
860 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
147 ms |
1080 KB |
Output isn't correct |
| 7 |
Correct |
3 ms |
856 KB |
Output is correct |
| 8 |
Incorrect |
135 ms |
1260 KB |
Output isn't correct |
| 9 |
Correct |
4 ms |
1080 KB |
Output is correct |
| 10 |
Correct |
9 ms |
1324 KB |
Output is correct |
| 11 |
Correct |
7 ms |
1116 KB |
Output is correct |
| 12 |
Execution timed out |
3098 ms |
460 KB |
Time limit exceeded |
| 13 |
Execution timed out |
3069 ms |
604 KB |
Time limit exceeded |
| 14 |
Correct |
107 ms |
3676 KB |
Output is correct |
| 15 |
Execution timed out |
3069 ms |
604 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3041 ms |
604 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3053 ms |
604 KB |
Time limit exceeded |
| 18 |
Correct |
153 ms |
4696 KB |
Output is correct |
| 19 |
Execution timed out |
3063 ms |
600 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3015 ms |
856 KB |
Time limit exceeded |
