7792022-01-11 10:28:24Halasz EszterRácsháló gráfcpp11Accepted 50/5012ms2308 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;
}
SubtaskSumTestVerdictTimeMemory
base50/50
1Accepted0/02ms1828 KiB
2Accepted0/012ms2196 KiB
3Accepted2/22ms1972 KiB
4Accepted2/22ms1980 KiB
5Accepted2/22ms1980 KiB
6Accepted2/22ms1984 KiB
7Accepted2/22ms2048 KiB
8Accepted2/22ms2052 KiB
9Accepted2/22ms2060 KiB
10Accepted2/22ms2024 KiB
11Accepted2/22ms2064 KiB
12Accepted2/24ms2264 KiB
13Accepted3/36ms2232 KiB
14Accepted3/32ms2076 KiB
15Accepted3/36ms2112 KiB
16Accepted3/32ms2084 KiB
17Accepted3/34ms2112 KiB
18Accepted3/33ms2080 KiB
19Accepted3/32ms2044 KiB
20Accepted3/32ms2056 KiB
21Accepted3/33ms2096 KiB
22Accepted3/312ms2308 KiB