53202023-04-25 21:57:11CattVázsony vonatjegyet vásárolcpp17Futási hiba 20/1001.575s194280 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(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
1Elfogadva12ms27016 KiB
2Elfogadva199ms63232 KiB
subtask220/20
3Elfogadva93ms47596 KiB
4Elfogadva633ms133268 KiB
5Elfogadva537ms120088 KiB
6Elfogadva370ms108132 KiB
7Elfogadva507ms130224 KiB
8Elfogadva342ms118548 KiB
9Elfogadva981ms194280 KiB
subtask30/15
10Futási hiba303ms130468 KiB
11Elfogadva30ms84860 KiB
12Időlimit túllépés1.557s70376 KiB
13Időlimit túllépés1.562s75940 KiB
14Időlimit túllépés1.575s85476 KiB
subtask40/20
15Futási hiba70ms107084 KiB
16Futási hiba305ms142908 KiB
17Elfogadva61ms105752 KiB
18Elfogadva107ms117396 KiB
19Elfogadva52ms102652 KiB
20Elfogadva104ms113840 KiB
subtask50/45
21Időlimit túllépés1.55s79008 KiB
22Időlimit túllépés1.554s131736 KiB
23Elfogadva90ms73528 KiB
24Elfogadva404ms115572 KiB
25Elfogadva370ms113620 KiB
26Elfogadva560ms139300 KiB
27Elfogadva296ms104280 KiB
28Elfogadva1.184s193980 KiB
29Elfogadva196ms90080 KiB
30Elfogadva930ms185868 KiB
31Futási hiba314ms114756 KiB
32Időlimit túllépés1.567s55284 KiB
33Futási hiba507ms137280 KiB
34Elfogadva411ms114240 KiB
35Elfogadva428ms112520 KiB
36Elfogadva458ms111464 KiB
37Elfogadva462ms111040 KiB