#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)
{
// cout<<"a: "<<a+1<<" b: "<<b+1<<endl;
if(vis[a][b][dir])return dp[a][b][dir];
int res=0;
for(int i=(a+1)%n; i!=b; i=(i+1)%n)
{
if(i==n)i=0;
if(i==b)break;
int prev=(dir?b:a);
if(mat[prev][i])
{
res=max(res,f(a,i,1)+1);
res=max(res,f(i,b,0)+1);
}
}
vis[a][b][dir]=true;
dp[a][b][dir]=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()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
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++)
{
for(int j=0; j<n; j++)
{
if(mat[i][j])
{
int tmp=f(i,j,0);
if(res<tmp)
{
res=tmp;
poz=i;
}
tmp=f(j,i,1);
if(res<tmp)
{
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 dirgore;
if((d<b && d>a) || (d<b && d<a))dirgore=1;
else dirgore=0;
int gore=f(d,b,dirgore);
int dolu=f(d,a,!dirgore);
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:163:26: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
163 | cout<<mxx<<endl<<poz+1<<endl;
| ^
race.cpp:108:30: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
108 | cout<<res<<endl<<poz+1<<endl;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
604 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
604 KB |
Output isn't correct |
| 4 |
Incorrect |
10 ms |
964 KB |
Output isn't correct |
| 5 |
Correct |
1 ms |
860 KB |
Output is correct |
| 6 |
Incorrect |
155 ms |
1056 KB |
Output isn't correct |
| 7 |
Incorrect |
3 ms |
856 KB |
Output isn't correct |
| 8 |
Incorrect |
132 ms |
1192 KB |
Output isn't correct |
| 9 |
Incorrect |
4 ms |
1116 KB |
Output isn't correct |
| 10 |
Incorrect |
5 ms |
1116 KB |
Output isn't correct |
| 11 |
Incorrect |
8 ms |
1112 KB |
Output isn't correct |
| 12 |
Execution timed out |
3034 ms |
344 KB |
Time limit exceeded |
| 13 |
Execution timed out |
3087 ms |
600 KB |
Time limit exceeded |
| 14 |
Incorrect |
217 ms |
3664 KB |
Output isn't correct |
| 15 |
Execution timed out |
3029 ms |
600 KB |
Time limit exceeded |
| 16 |
Execution timed out |
3059 ms |
600 KB |
Time limit exceeded |
| 17 |
Execution timed out |
3061 ms |
604 KB |
Time limit exceeded |
| 18 |
Incorrect |
371 ms |
4564 KB |
Output isn't correct |
| 19 |
Execution timed out |
3082 ms |
600 KB |
Time limit exceeded |
| 20 |
Execution timed out |
3046 ms |
856 KB |
Time limit exceeded |
