147342025-01-30 11:27:05ercseferencA lehető legkevesebb metróval utazás (40 pont)cpp17Wrong answer 22/40601ms6708 KiB
#include <bits/stdc++.h>
using namespace std;
int n,m;
struct allomas{vector<int>metro;};
struct metro{vector<int>kim,his; bool van[201]; bool vane=0;};
bool megold[201];
int main()
{
    int ind,erk,x,y;
    cin>>n>>m>>ind>>erk;
    vector<allomas>a(m+1); vector<metro>b(n+1);
    for(int i=0; i<n; i++){
        cin>>x;
        for(int j=0; j<x; j++){
            cin>>y; a[y].metro.push_back(i+1);}}
    for(int i=1; i<=n; i++){b[i].van[i]=1;}
    for(int i=1; i<=m; i++){
        if(a[i].metro.size()>1){
            for(int j=0; j<a[i].metro.size(); j++){
                for(int k=0; k<a[i].metro.size(); k++){
                    if(b[a[i].metro[j]].van[a[i].metro[k]]==0){
                        b[a[i].metro[j]].van[a[i].metro[k]]=1;
                        b[a[i].metro[j]].kim.push_back(a[i].metro[k]);}}}}}
    vector<int>l1,l2; int jometr;
    for(int i=0; i<a[erk].metro.size(); i++){megold[a[erk].metro[i]]=1;}
    for(int i=0; i<a[ind].metro.size(); i++){l1.push_back(a[ind].metro[i]);
        b[a[ind].metro[i]].his.push_back(a[ind].metro[i]);}
    bool nincs=0, megvan=0; b[0].vane=1;
    while(!nincs && !megvan){
        for(int i=0; i<l1.size(); i++){
            for(int j=0; j<b[l1[i]].kim.size(); j++){
                if(b[b[l1[i]].kim[j]].vane==0){
                    b[b[l1[i]].kim[j]].vane=1;
                    b[b[l1[i]].kim[j]].his=b[l1[i]].his;
                    b[b[l1[i]].kim[j]].his.push_back(b[l1[i]].kim[j]);
                    l2.push_back(b[l1[i]].kim[j]);}}}
        for(int i=0; i<l2.size(); i++){if(megold[l2[i]]==1){megvan=1; jometr=l2[i];}}
        if(l2.size()==0)nincs=1;
        l1=l2; l2.clear();}
    cout<<b[jometr].his.size()<<endl;
    for(int i=0; i<b[jometr].his.size(); i++){cout<<b[jometr].his[i]<<" ";}
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base22/40
1Accepted0/01ms512 KiB
2Accepted0/06ms1076 KiB
3Wrong answer0/21ms316 KiB
4Accepted2/21ms316 KiB
5Wrong answer0/21ms316 KiB
6Wrong answer0/21ms316 KiB
7Accepted2/22ms316 KiB
8Accepted2/22ms564 KiB
9Accepted2/24ms744 KiB
10Accepted2/24ms584 KiB
11Accepted2/22ms316 KiB
12Wrong answer0/27ms932 KiB
13Wrong answer0/27ms928 KiB
14Accepted2/26ms1076 KiB
15Time limit exceeded0/2601ms6556 KiB
16Time limit exceeded0/2573ms6704 KiB
17Time limit exceeded0/2600ms6708 KiB
18Time limit exceeded0/2600ms6700 KiB
19Accepted2/24ms820 KiB
20Accepted2/24ms820 KiB
21Accepted2/23ms564 KiB
22Accepted2/26ms1036 KiB