53212023-04-25 22:00:18CattVázsony vonatjegyet vásárolcpp17Futási hiba 20/1001.574s231872 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]) 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[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] && s[cur] > s[parent[sz]]) || 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
1Elfogadva14ms26868 KiB
2Elfogadva216ms63144 KiB
subtask220/20
3Elfogadva92ms47504 KiB
4Elfogadva649ms133120 KiB
5Elfogadva474ms120260 KiB
6Elfogadva375ms106200 KiB
7Elfogadva439ms121448 KiB
8Elfogadva356ms104500 KiB
9Elfogadva968ms169104 KiB
subtask30/15
10Futási hiba307ms105256 KiB
11Elfogadva28ms59360 KiB
12Időlimit túllépés1.562s44792 KiB
13Időlimit túllépés1.574s50292 KiB
14Időlimit túllépés1.57s59940 KiB
subtask40/20
15Futási hiba70ms81476 KiB
16Futási hiba277ms117668 KiB
17Elfogadva63ms80272 KiB
18Elfogadva93ms90620 KiB
19Elfogadva46ms75396 KiB
20Elfogadva101ms85504 KiB
subtask50/45
21Időlimit túllépés1.574s50380 KiB
22Elfogadva1.355s231872 KiB
23Elfogadva85ms73588 KiB
24Elfogadva351ms115468 KiB
25Elfogadva368ms113640 KiB
26Elfogadva611ms139216 KiB
27Elfogadva293ms104192 KiB
28Elfogadva1.101s193896 KiB
29Elfogadva195ms89896 KiB
30Elfogadva1.225s185676 KiB
31Futási hiba279ms114944 KiB
32Időlimit túllépés1.57s55684 KiB
33Futási hiba507ms137672 KiB
34Elfogadva405ms114644 KiB
35Elfogadva442ms112844 KiB
36Elfogadva400ms111796 KiB
37Elfogadva451ms111272 KiB