85892024-01-22 21:17:41zeytonxA lehető legkevesebb metróval utazás (40 pont)cpp17Hibás válasz 26/40601ms21384 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define endl "\n"
#define pll pair<ll,ll>
#define vll vector<ll>
#define mll map<ll,ll>
#define fs first
#define sc second

const ll MOD = 1e9+7;


void solve()
{
	ll n, m, ind, erk;
	cin >> n >> m >> ind >> erk;
    ind--; erk--;
	map<ll,set<ll>> l;
    map<ll,set<ll>> s;
    map<ll,set<ll>> e;
    map<ll,bool> erk_stat;
    for(ll i = 0; i < n; i++)
    {
        ll k;
        cin >> k;
        for(ll j = 0; j < k; j++)
        {
            ll inp;
            cin >> inp;
            inp--;
            if(inp == erk)
            {
                erk_stat[i] = true;
            }
            l[i].insert(inp);
            for(ll p : s[inp])
            {
                e[i].insert(p);
                e[p].insert(i);
            }
            s[inp].insert(i);
        }
    }
    map<ll, vector<ll>> ans;
    queue<ll> q;
    for(ll i : s[ind])
    {
        q.push(i);
        ans[i] = {i};
    }
    ll min_v = LLONG_MAX;
    ll min_index = 0;
    while(!q.empty())
    {
        ll p = q.front();
        q.pop();
        for(ll p2 : e[p])
        {
            if(ans[p2].size() == 0 || ans[p2].size() > ans[p].size()+1)
            {
                ans[p2] = ans[p];
                ans[p2].push_back(p2);
                
                if(!erk_stat[p2])
                    q.push(p2);
                else
                {
                    if(ans[p2].size() < min_v)
                    {
                        min_v = ans[p2].size();
                        min_index = p2;
                    }
                }
            }
        }
    }
    cout << min_v << endl;
    for(ll i : ans[min_index]) cout << i+1 << " ";
    cout << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--)
        solve();
    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base26/40
1Elfogadva0/03ms2080 KiB
2Elfogadva0/013ms7052 KiB
3Hibás válasz0/23ms2328 KiB
4Elfogadva2/23ms2500 KiB
5Hibás válasz0/23ms3212 KiB
6Hibás válasz0/23ms2972 KiB
7Elfogadva2/24ms3984 KiB
8Elfogadva2/24ms4232 KiB
9Elfogadva2/28ms5820 KiB
10Elfogadva2/27ms5600 KiB
11Elfogadva2/24ms4244 KiB
12Elfogadva2/213ms8260 KiB
13Elfogadva2/213ms8244 KiB
14Elfogadva2/213ms7948 KiB
15Időlimit túllépés0/2601ms20188 KiB
16Időlimit túllépés0/2566ms21384 KiB
17Időlimit túllépés0/2566ms20896 KiB
18Időlimit túllépés0/2570ms21240 KiB
19Elfogadva2/28ms6532 KiB
20Elfogadva2/210ms7668 KiB
21Elfogadva2/27ms5480 KiB
22Elfogadva2/213ms7940 KiB