1302 | 2022. 04. 09 22:06:09 | ZsofiaKeresztely | Pletyka | cpp14 | Időlimit túllépés 82/100 | 186ms | 26696 KiB |
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
int main() {
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 | 82/100 | ||||||
1 | Elfogadva | 0/0 | 2ms | 1796 KiB | |||
2 | Elfogadva | 0/0 | 32ms | 6232 KiB | |||
3 | Elfogadva | 2/2 | 1ms | 2184 KiB | |||
4 | Elfogadva | 2/2 | 2ms | 2252 KiB | |||
5 | Elfogadva | 2/2 | 3ms | 2472 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 2956 KiB | |||
7 | Elfogadva | 4/4 | 4ms | 3000 KiB | |||
8 | Elfogadva | 4/4 | 8ms | 3688 KiB | |||
9 | Elfogadva | 4/4 | 9ms | 3784 KiB | |||
10 | Elfogadva | 4/4 | 8ms | 3880 KiB | |||
11 | Elfogadva | 4/4 | 30ms | 6968 KiB | |||
12 | Elfogadva | 4/4 | 28ms | 7300 KiB | |||
13 | Elfogadva | 4/4 | 52ms | 10772 KiB | |||
14 | Elfogadva | 4/4 | 52ms | 11408 KiB | |||
15 | Elfogadva | 6/6 | 78ms | 14992 KiB | |||
16 | Elfogadva | 6/6 | 70ms | 15800 KiB | |||
17 | Elfogadva | 6/6 | 86ms | 19616 KiB | |||
18 | Elfogadva | 6/6 | 109ms | 20740 KiB | |||
19 | Elfogadva | 6/6 | 115ms | 23096 KiB | |||
20 | Elfogadva | 6/6 | 112ms | 24352 KiB | |||
21 | Elfogadva | 6/6 | 115ms | 25516 KiB | |||
22 | Időlimit túllépés | 0/6 | 126ms | 26696 KiB | |||
23 | Időlimit túllépés | 0/6 | 170ms | 21996 KiB | |||
24 | Időlimit túllépés | 0/6 | 186ms | 25032 KiB |