53242023-04-25 22:05:15CattVázsony vonatjegyet vásárolcpp17Futási hiba 20/1001.577s165440 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);
vector<bool> volt(maxN, 0);

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});
        }
    }
}

void dfs(int x) {
    volt[x] = 1;
    for(int sz : to[x]) {
        if(volt[root(sz)]) continue;
        dfs(root(sz));
    }
}

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);
            }
        }
    }
    dfs(root(a));
    vector<ll> be(n+1, 0);
    for(ll i = 1; i <= n; i++) {

        if(!volt[i] || root(i) != i) continue;
        for(ll sz : to[i]) be[root(sz)]++;
    }

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

        volt[cur] = 1;

        for(ll sz : to[cur]) {
            sz = root(sz);
            if(volt[sz]) continue;
            be[sz]--;
            if(tav[sz] < tav[cur] + s[cur]) {
                tav[sz] = tav[cur] + s[cur];
                parent[sz] = cur;
            }
            if(be[sz] == 0) {
                sor.push(sz);
            }
        }
    }

    set<ll> mo = {b};
    ll cur = b;
    while(cur != a) {
        cur = parent[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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva10ms26868 KiB
2Elfogadva211ms60196 KiB
subtask220/20
3Elfogadva92ms43232 KiB
4Elfogadva625ms119884 KiB
5Elfogadva535ms99620 KiB
6Elfogadva324ms82652 KiB
7Elfogadva503ms97996 KiB
8Elfogadva360ms81000 KiB
9Elfogadva982ms145468 KiB
subtask30/15
10Futási hiba307ms77188 KiB
11Elfogadva27ms31656 KiB
12Időlimit túllépés1.577s16740 KiB
13Időlimit túllépés1.554s21088 KiB
14Időlimit túllépés1.575s28764 KiB
subtask40/20
15Futási hiba82ms49284 KiB
16Futási hiba337ms82824 KiB
17Elfogadva63ms45112 KiB
18Elfogadva104ms55564 KiB
19Elfogadva52ms40344 KiB
20Elfogadva103ms50708 KiB
subtask50/45
21Időlimit túllépés1.552s15472 KiB
22Időlimit túllépés1.565s102368 KiB
23Elfogadva86ms44512 KiB
24Elfogadva358ms86456 KiB
25Elfogadva328ms84736 KiB
26Elfogadva529ms110500 KiB
27Elfogadva266ms75484 KiB
28Elfogadva981ms165440 KiB
29Elfogadva182ms61400 KiB
30Elfogadva925ms157240 KiB
31Futási hiba312ms86244 KiB
32Időlimit túllépés1.567s26772 KiB
33Futási hiba446ms108956 KiB
34Elfogadva400ms86056 KiB
35Elfogadva449ms83924 KiB
36Elfogadva437ms82884 KiB
37Elfogadva400ms82360 KiB