139222025-01-09 11:13:21ercseferencFertőzési sorozat (50 pont)cpp17Hibás válasz 44/5019ms1516 KiB
#include <bits/stdc++.h>
using namespace std;
struct ember{vector<int>kim; int tav[501]={}; bool van;};
bool nov(vector<int>a){
    if(a[0]<1)return false;
    for(int i=1; i<a.size(); i++){
        if(!(a[i]-a[i-1]<2 && a[i]-a[i-1]>=0))return 0;}
    return true;}
bool valid(vector<int>v1){
    int n=v1[0]; int k=0;
    if(n==-1 || n==0)return 0;
    while(v1[k]==n && k<v1.size()){k++;}
    if(k==v1.size())return 1;
    else{
        if(v1[k]!=n+1)return 0;
        else{
            n++;
            while(k<v1.size()){
                if(v1[k]!=n)return 0;
                k++;}}}
    return 1;}
int elso(vector<int>a){
    int i=0;
    while(a[i]==0){i++;}
    return i;}
vector<int>sorba(vector<int>a){
    int c=a[a.size()-1];
    vector<int>b(c+1);
    for(int i=0; i<a.size(); i++){b[a[i]]++;}
    return b;}
int main()
{
    int n,m,k,x,y; //ifstream f("szamok.txt");
    cin>>n>>m>>k;
    int kezd[k]; vector<int>l1,l2; vector<ember>a(n+1);
    for(int i=0; i<k; i++){cin>>kezd[i];}
    for(int i=0; i<m; i++){cin>>x>>y;
        a[x].kim.push_back(y);
        a[y].kim.push_back(x);}
    for(int i=0; i<k; i++){
        l1.clear(); l2.clear(); l1.push_back(kezd[i]);
        for(int j=1; j<=n; j++){a[j].van=0;}
        a[kezd[i]].van=1; int p=1; bool nincs=0;
        a[kezd[i]].tav[kezd[i]]=-1;
        while(!nincs){
            for(int j=0; j<l1.size(); j++){
                for(int v=0; v<a[l1[j]].kim.size(); v++){
                    if(a[a[l1[j]].kim[v]].van==0){
                        l2.push_back(a[l1[j]].kim[v]);
                        a[a[l1[j]].kim[v]].van=1;
                        a[kezd[i]].tav[a[l1[j]].kim[v]]=p;}}}
            if(l2.size()==0)nincs=1;
            l1.clear(); l1=l2; l2.clear(); p++;}}
    vector<int>megold,szamok; int s,maxi,mini;
    for(int i=1; i<=n; i++){
        szamok.clear();
        for(int j=0; j<k; j++){
            szamok.push_back(a[kezd[j]].tav[i]);}
        if(valid(szamok))megold.push_back(i);
        else if(nov(szamok)){
            vector<int>c=sorba(szamok);
            int els=elso(c)+1,uts=c.size()-2,p=1; bool helyes=1;
            l1.clear(); l2.clear(); l1.push_back(i); bool nincs=0;
            for(int j=1; j<=n; j++){a[j].van=0;} a[i].van=1;
            vector<int>jonov; jonov.clear();
            while(!nincs){
                for(int j=0; j<l1.size(); j++){
                    for(int v=0; v<a[l1[j]].kim.size(); v++){
                        if(a[a[l1[j]].kim[v]].van==0){
                            l2.push_back(a[l1[j]].kim[v]);
                            a[a[l1[j]].kim[v]].van=1;
                            jonov.push_back(p);}}}
                if(l2.size()==0)nincs=1;
                l1.clear(); l1=l2; l2.clear(); p++;}
            vector<int>d=sorba(jonov);
            for(int j=els; j<=uts; j++){if(c[j]!=d[j])helyes=0;}
            if(helyes)megold.push_back(i);}}
    cout<<megold.size()<<endl;
    for(int i=0; i<megold.size(); i++){cout<<megold[i]<<" ";}
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base44/50
1Elfogadva0/01ms316 KiB
2Elfogadva0/01ms316 KiB
3Elfogadva0/02ms1004 KiB
4Hibás válasz0/21ms508 KiB
5Elfogadva2/21ms492 KiB
6Elfogadva2/22ms820 KiB
7Elfogadva2/22ms820 KiB
8Elfogadva2/22ms916 KiB
9Hibás válasz0/22ms820 KiB
10Elfogadva2/23ms1332 KiB
11Hibás válasz0/11ms316 KiB
12Elfogadva2/22ms1332 KiB
13Elfogadva2/22ms1332 KiB
14Elfogadva2/22ms1332 KiB
15Elfogadva2/22ms1388 KiB
16Elfogadva2/22ms1332 KiB
17Elfogadva2/22ms1336 KiB
18Elfogadva1/14ms1416 KiB
19Elfogadva1/12ms1368 KiB
20Elfogadva1/12ms1408 KiB
21Elfogadva1/14ms1440 KiB
22Elfogadva1/14ms1428 KiB
23Elfogadva1/14ms1428 KiB
24Elfogadva1/13ms1428 KiB
25Elfogadva1/14ms1332 KiB
26Elfogadva1/14ms1516 KiB
27Elfogadva1/13ms1516 KiB
28Elfogadva1/13ms1332 KiB
29Elfogadva1/13ms1332 KiB
30Elfogadva1/13ms1360 KiB
31Elfogadva1/13ms1332 KiB
32Elfogadva1/13ms1332 KiB
33Hibás válasz0/119ms1260 KiB
34Elfogadva1/13ms1240 KiB
35Elfogadva1/13ms1332 KiB
36Elfogadva1/13ms1332 KiB
37Elfogadva1/13ms1332 KiB
38Elfogadva1/13ms1332 KiB
39Elfogadva1/13ms1332 KiB
40Elfogadva1/110ms1332 KiB