1303 | 2022. 04. 09 22:07:30 | ZsofiaKeresztely | Pletyka | cpp14 | Elfogadva 100/100 | 108ms | 34364 KiB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k, c=0;
cin>>n>>m>>k;
vector<vector<int> > g(n+1);
vector<vector<bool> > volt(2, vector<bool>(n+1, false));
vector<vector<int> > tav(2, vector<int>(n+1, 0));
vector<int> napok(2*n, 0);
vector<int> merges(k);
queue<pair<int, int> > q; //sorszama, paritas
for (int i=0; i<k; i++)
{
cin>>merges[i];
q.push(mp(merges[i], 0));
volt[0][merges[i]]=true;
}
int a, b;
for (int i=0; i<m; i++)
{
cin>>a>>b;
g[a].push_back(b);
g[b].push_back(a);
}
for (int x : merges)
{
if (!g[x].size())
{
c++;
}
}
pair<int, int> elso;
while (!q.empty())
{
elso=q.front();
q.pop();
for (int x : g[elso.first])
{
if (!volt[1-elso.second][x])
{
volt[1-elso.second][x]=true;
q.push(mp(x, 1-elso.second));
tav[1-elso.second][x]=tav[elso.second][elso.first]+1;
napok[tav[1-elso.second][x]]++;
}
}
}
napok[0]=k-c;
int maxi=0;
if (napok[1]>napok[maxi])
{
maxi=1;
}
for (int i=2; i<2*n; i++)
{
napok[i]+=napok[i-2];
if (napok[i]>napok[maxi])
{
maxi=i;
}
}
if (k>napok[maxi])
{
maxi=0;
}
napok[0]=k;
cout<<napok[maxi]<<"\n"<<maxi+1<<"\n";
for (int i=0; i<=maxi; i++)
{
cout<<napok[i]<<" ";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1812 KiB | |||
2 | Elfogadva | 0/0 | 17ms | 6224 KiB | |||
3 | Elfogadva | 2/2 | 1ms | 2204 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2280 KiB | |||
5 | Elfogadva | 2/2 | 2ms | 2492 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 2976 KiB | |||
7 | Elfogadva | 4/4 | 4ms | 3020 KiB | |||
8 | Elfogadva | 4/4 | 6ms | 3688 KiB | |||
9 | Elfogadva | 4/4 | 4ms | 3788 KiB | |||
10 | Elfogadva | 4/4 | 4ms | 3884 KiB | |||
11 | Elfogadva | 4/4 | 17ms | 6964 KiB | |||
12 | Elfogadva | 4/4 | 16ms | 7300 KiB | |||
13 | Elfogadva | 4/4 | 28ms | 10852 KiB | |||
14 | Elfogadva | 4/4 | 32ms | 11440 KiB | |||
15 | Elfogadva | 6/6 | 46ms | 15092 KiB | |||
16 | Elfogadva | 6/6 | 43ms | 15908 KiB | |||
17 | Elfogadva | 6/6 | 71ms | 19756 KiB | |||
18 | Elfogadva | 6/6 | 63ms | 20804 KiB | |||
19 | Elfogadva | 6/6 | 57ms | 23240 KiB | |||
20 | Elfogadva | 6/6 | 74ms | 24416 KiB | |||
21 | Elfogadva | 6/6 | 75ms | 25556 KiB | |||
22 | Elfogadva | 6/6 | 74ms | 26724 KiB | |||
23 | Elfogadva | 6/6 | 108ms | 32052 KiB | |||
24 | Elfogadva | 6/6 | 103ms | 34364 KiB |