779 2022. 01. 11 10:28:24 Halasz Eszter Rácsháló gráf cpp11 Elfogadva 50/50 12ms 2308 KiB
#include <iostream>
//#include <fstream>
#include <algorithm>

using namespace std;

//ifstream cin("racshalo.in");
//ofstream cout("racshalo.out");

int n,m,k,i,j,x[201][201],ax,ay,bx,by,a,b,maxi,p,q;

int main()
{
    cin>>n>>m>>k;
    for(i=1;i<=n*m;++i)
    {
        for(j=1;j<=n*m;++j)
        {
            if(j>i)
            {
                ax=i/m;
                if(i%m!=0) ax++;

                ay=i%m;
                if(i%m==0) ay=m;

                bx=j/m;
                if(j%m!=0) bx++;

                by=j%m;
                if(j%m==0) by=m;



                x[i][j]=abs(ax-bx)+abs(ay-by);
                x[j][i]=x[i][j];

            }
        }
    }

   /* for(i=1;i<=n*m;++i)
    {
        for(j=1;j<=n*m;++j)
            cout<<x[i][j]<<" ";
        cout<<"\n";
    }*/


    while(k>0)
    {
        cin>>a>>b;
        x[a][b]=x[b][a]=1;
        maxi=-1;
        for(i=1;i<=n*m;++i)
        {
            for(j=1;j<=n*m;++j)
            {
                if(j>i)
                {
                    p=x[i][a]+x[a][b]+x[b][j];
                    q=x[i][b]+x[b][a]+x[a][j];
                    x[i][j]=min(p,x[i][j]);
                    x[i][j]=min(q,x[i][j]);
                    x[j][i]=x[i][j];
                    if(x[i][j]>maxi) maxi=x[i][j];
                }
            }
        }

        cout<<maxi<<"\n";
        k--;
    }


    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 2ms 1828 KiB
2 Elfogadva 0/0 12ms 2196 KiB
3 Elfogadva 2/2 2ms 1972 KiB
4 Elfogadva 2/2 2ms 1980 KiB
5 Elfogadva 2/2 2ms 1980 KiB
6 Elfogadva 2/2 2ms 1984 KiB
7 Elfogadva 2/2 2ms 2048 KiB
8 Elfogadva 2/2 2ms 2052 KiB
9 Elfogadva 2/2 2ms 2060 KiB
10 Elfogadva 2/2 2ms 2024 KiB
11 Elfogadva 2/2 2ms 2064 KiB
12 Elfogadva 2/2 4ms 2264 KiB
13 Elfogadva 3/3 6ms 2232 KiB
14 Elfogadva 3/3 2ms 2076 KiB
15 Elfogadva 3/3 6ms 2112 KiB
16 Elfogadva 3/3 2ms 2084 KiB
17 Elfogadva 3/3 4ms 2112 KiB
18 Elfogadva 3/3 3ms 2080 KiB
19 Elfogadva 3/3 2ms 2044 KiB
20 Elfogadva 3/3 2ms 2056 KiB
21 Elfogadva 3/3 3ms 2096 KiB
22 Elfogadva 3/3 12ms 2308 KiB