Submission #1091455

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091455		AtinaR	Sailing Race (CEOI12_race)	C++14	0 / 100	3065 ms	4420 KiB

race

#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 x=f(6,4,6);
    //cout<<"odg "<<x<<endl;
    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 (stderr)

race.cpp: In function 'int main()':
race.cpp:94:13: warning: variable 'poz' set but not used [-Wunused-but-set-variable]
   94 |         int poz,res=0;
      |             ^~~
race.cpp:112:9: warning: unused variable 'x' [-Wunused-variable]
  112 |     int x=f(6,4,6);
      |         ^
race.cpp:158:26: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  158 |     cout<<mxx<<endl<<poz+1<<endl;
      |                          ^

• Subtask 1: 0 / 100