5317 2023. 04. 25 21:26:12 Catt Vázsony vonatjegyet vásárol cpp17 Időlimit túllépés 0/100 1.6s 131800 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll maxN = 2e5 + 5;


vector<vector<pair<ll, ll> > > g;
vector<ll> dist;
vector<ll> p(maxN), s(maxN, 1);
vector<set<ll> > to(maxN);

ll root(ll x) {
    if(p[x] == x) return x;

    return p[x] = root(p[x]);
}

void connect(ll x, ll y) {
    x = root(x);
    y = root(y);

    if(x == y) return;
    if(to[x].size() < to[y].size()) swap(x, y);

    p[y] = x;
    for(ll sz : to[y]) {
        to[x].insert(sz);
    }
    s[x] += s[y];
}

void dijkstra(ll start) {
    priority_queue<pair<ll, ll> > pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();

        ll w = -curr.first, x = curr.second;
        if(dist[x] != -1) continue;
        dist[x] = w;
        for(pair<ll, ll> sz : g[x]) {
            if(dist[sz.first] != -1) continue;
            pq.push({-w-sz.second, sz.first});
        }
    }
}

int main() {

    ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    
    ll n,m,a,b;
    cin >> n >> m >> a >> b;
    g.resize(n+1);
    dist.resize(n+1, -1);

    for(ll i = 0; i < m; i++) {
        ll x,y,z;
        cin >> x >> y >> z;

        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }


    dijkstra(b);
    for(ll i = 1; i <= n; i++) {
        p[i] = i;
        for(auto sz : g[i]) {
            if(dist[sz.first] < dist[i]) {
                to[i].insert(sz.first);
            }
            else if(dist[sz.first] > dist[i]) {
                to[sz.first].insert(i);
            }
        }
    }
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] == dist[i]) {
                connect(sz.first, i);
            }
        }
    }
    vector<ll> be(n+1, 0);
    for(ll i = 1; i <= n; i++) {
        for(ll sz : to[i]) be[root(sz)]++;
    }

    vector<ll> tav(n+1, -1), parent(n+1, -1);
    queue<ll> sor;
    sor.push(root(a));
    while(!sor.empty()) {
        ll cur = sor.front();
        sor.pop();

        for(ll sz : to[cur]) {
            sz = root(sz);
            be[sz]--;
            if((tav[sz] == tav[cur] + 1 && s[cur] > s[p[sz]]) || tav[sz] < tav[cur] + 1) {
                tav[sz] = tav[cur] + 1;
                p[sz] = cur;
            }
            tav[sz] = max(tav[sz], tav[cur] + 1);

            if(be[sz] == 0) {
                sor.push(sz);
            }
        }
    }

    set<ll> mo = {b};
    ll cur = b;
    while(cur != a) {
        cur = p[cur];
        mo.insert(cur);
    }

    vector<ll> ki;
    for(ll i = 1; i <= n; i++) {
        if(mo.find(root(i)) != mo.end()) ki.push_back(i);
    }

    cout << ki.size() << "\n";
    for(ll sz : ki) cout << sz << ' ';
    
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 14ms 26876 KiB
2 Időlimit túllépés 1.6s 33364 KiB
subtask2 0/20
3 Időlimit túllépés 1.557s 26432 KiB
4 Időlimit túllépés 1.565s 73896 KiB
5 Időlimit túllépés 1.562s 71288 KiB
6 Időlimit túllépés 1.569s 67884 KiB
7 Időlimit túllépés 1.569s 82332 KiB
8 Időlimit túllépés 1.578s 79160 KiB
9 Időlimit túllépés 1.572s 122932 KiB
subtask3 0/15
10 Időlimit túllépés 1.58s 92960 KiB
11 Elfogadva 30ms 85492 KiB
12 Időlimit túllépés 1.577s 70704 KiB
13 Időlimit túllépés 1.57s 76312 KiB
14 Időlimit túllépés 1.559s 85784 KiB
subtask4 0/20
15 Időlimit túllépés 1.523s 80288 KiB
16 Időlimit túllépés 1.56s 102528 KiB
17 Időlimit túllépés 1.58s 81516 KiB
18 Időlimit túllépés 1.526s 88228 KiB
19 Időlimit túllépés 1.6s 83472 KiB
20 Időlimit túllépés 1.565s 89600 KiB
subtask5 0/45
21 Időlimit túllépés 1.569s 79236 KiB
22 Időlimit túllépés 1.575s 131752 KiB
23 Időlimit túllépés 1.57s 53660 KiB
24 Időlimit túllépés 1.567s 79156 KiB
25 Időlimit túllépés 1.562s 82700 KiB
26 Időlimit túllépés 1.588s 101960 KiB
27 Időlimit túllépés 1.582s 88268 KiB
28 Időlimit túllépés 1.569s 131732 KiB
29 Időlimit túllépés 1.524s 82808 KiB
30 Időlimit túllépés 1.562s 131800 KiB
31 Időlimit túllépés 1.557s 99608 KiB
32 Időlimit túllépés 1.554s 82892 KiB
33 Időlimit túllépés 1.577s 116816 KiB
34 Időlimit túllépés 1.534s 109000 KiB
35 Időlimit túllépés 1.559s 114896 KiB
36 Időlimit túllépés 1.562s 120536 KiB
37 Időlimit túllépés 1.577s 126136 KiB