829 | 2022. 01. 18 21:44:26 | Halasz Eszter | Ciklikus rácsháló gráf | cpp11 | Elfogadva 40/40 | 57ms | 2220 KiB |
#include <iostream>
//#include <fstream>
#include <algorithm>
#include <deque>
#include <vector>
using namespace std;
//ifstream cin("ciklikusracshalograf.in");
//ofstream cout("ciklikusracshalograf.out");
deque<int>y;
struct adat
{
int x,y;
};
adat a,b,q;
struct adat2
{
int lat,lep;
vector<int>sz;
};
vector<adat2>x;
int i,j,n,m,k,maxii=-9999,aa,bb;
void maxi(int a)
{
int i;
for(i=1;i<=n*m;++i)
if(x[i].lep>maxii) maxii=x[i].lep;
for(i=1;i<=n*m;++i)
{
x[i].lat=0;
}
}
void szelessegi(int i)
{
int csp=0;
y.push_back(i);
x[i].lep=0;
while(!y.empty())
{
csp=y.front();
y.pop_front();
for(auto e:x[csp].sz)
{
if(x[e].lat==0)
{
x[e].lat=1;
x[e].lep=x[csp].lep+1;
y.push_back(e);
}
else x[e].lep=min(x[e].lep,x[csp].lep+1);
}
}
}
int main()
{
cin>>n>>m>>k;
x.resize(n*m+1);
for(i=1;i<=n*m;++i)
{
for(j=1;j<=n*m;++j)
if(j>i)
{
if(i%m!=0) a.x=i/m+1;
else a.x=i/m;
if(j%m!=0) b.x=j/m+1;
else b.x=j/m;
a.y=i%m;
if(a.y==0) a.y=m;
b.y=j%m;
if(b.y==0) b.y=m;
if((a.y==1 && b.y==m && b.x==a.x) || (a.y==b.y && a.x==1 && b.x==n) || (abs(a.x-b.x)+abs(a.y-b.y)==1))
{
x[i].sz.push_back(j);
x[j].sz.push_back(i);
}
}
}
while(k)
{
cin>>aa>>bb;
x[aa].sz.push_back(bb);
x[bb].sz.push_back(aa);
maxii=-9999;
for(i=1;i<=n*m;++i)
{
szelessegi(i);
maxi(aa);
}
cout<<maxii<<"\n";
k--;
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 40/40 | ||||||
1 | Elfogadva | 0/0 | 3ms | 2108 KiB | |||
2 | Elfogadva | 0/0 | 57ms | 2116 KiB | |||
3 | Elfogadva | 2/2 | 1ms | 2136 KiB | |||
4 | Elfogadva | 2/2 | 1ms | 2140 KiB | |||
5 | Elfogadva | 2/2 | 2ms | 2144 KiB | |||
6 | Elfogadva | 2/2 | 2ms | 2144 KiB | |||
7 | Elfogadva | 2/2 | 4ms | 2156 KiB | |||
8 | Elfogadva | 2/2 | 3ms | 2160 KiB | |||
9 | Elfogadva | 2/2 | 4ms | 2164 KiB | |||
10 | Elfogadva | 2/2 | 2ms | 2164 KiB | |||
11 | Elfogadva | 2/2 | 4ms | 2168 KiB | |||
12 | Elfogadva | 2/2 | 12ms | 2176 KiB | |||
13 | Elfogadva | 2/2 | 30ms | 2180 KiB | |||
14 | Elfogadva | 2/2 | 4ms | 2188 KiB | |||
15 | Elfogadva | 2/2 | 27ms | 2188 KiB | |||
16 | Elfogadva | 2/2 | 4ms | 2192 KiB | |||
17 | Elfogadva | 2/2 | 23ms | 2200 KiB | |||
18 | Elfogadva | 2/2 | 9ms | 2200 KiB | |||
19 | Elfogadva | 2/2 | 2ms | 2204 KiB | |||
20 | Elfogadva | 2/2 | 2ms | 2204 KiB | |||
21 | Elfogadva | 2/2 | 10ms | 2216 KiB | |||
22 | Elfogadva | 2/2 | 57ms | 2220 KiB |