5324 2023. 04. 25 22:05:15 Catt Vázsony vonatjegyet vásárol cpp17 Futási hiba 20/100 1.577s 165440 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 10ms 26868 KiB
2 Elfogadva 211ms 60196 KiB
subtask2 20/20
3 Elfogadva 92ms 43232 KiB
4 Elfogadva 625ms 119884 KiB
5 Elfogadva 535ms 99620 KiB
6 Elfogadva 324ms 82652 KiB
7 Elfogadva 503ms 97996 KiB
8 Elfogadva 360ms 81000 KiB
9 Elfogadva 982ms 145468 KiB
subtask3 0/15
10 Futási hiba 307ms 77188 KiB
11 Elfogadva 27ms 31656 KiB
12 Időlimit túllépés 1.577s 16740 KiB
13 Időlimit túllépés 1.554s 21088 KiB
14 Időlimit túllépés 1.575s 28764 KiB
subtask4 0/20
15 Futási hiba 82ms 49284 KiB
16 Futási hiba 337ms 82824 KiB
17 Elfogadva 63ms 45112 KiB
18 Elfogadva 104ms 55564 KiB
19 Elfogadva 52ms 40344 KiB
20 Elfogadva 103ms 50708 KiB
subtask5 0/45
21 Időlimit túllépés 1.552s 15472 KiB
22 Időlimit túllépés 1.565s 102368 KiB
23 Elfogadva 86ms 44512 KiB
24 Elfogadva 358ms 86456 KiB
25 Elfogadva 328ms 84736 KiB
26 Elfogadva 529ms 110500 KiB
27 Elfogadva 266ms 75484 KiB
28 Elfogadva 981ms 165440 KiB
29 Elfogadva 182ms 61400 KiB
30 Elfogadva 925ms 157240 KiB
31 Futási hiba 312ms 86244 KiB
32 Időlimit túllépés 1.567s 26772 KiB
33 Futási hiba 446ms 108956 KiB
34 Elfogadva 400ms 86056 KiB
35 Elfogadva 449ms 83924 KiB
36 Elfogadva 437ms 82884 KiB
37 Elfogadva 400ms 82360 KiB