Submission #1091479

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091479		AtinaR	Sailing Race (CEOI12_race)	C++14	10 / 100	3088 ms	4436 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)
{
   // 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()
{
    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;
                    }
                }
            }
        }
        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 (stderr)

race.cpp: In function 'int main()':
race.cpp:154:26: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
  154 |     cout<<mxx<<endl<<poz+1<<endl;
      |                          ^
race.cpp:99:30: warning: 'poz' may be used uninitialized in this function [-Wmaybe-uninitialized]
   99 |         cout<<res<<endl<<poz+1<<endl;
      |                              ^

• Subtask 1: 10 / 100