53232023-04-25 22:02:54CattVázsony vonatjegyet vásárolcpp17Futási hiba 20/1001.582s202224 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] && 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
1Elfogadva13ms26868 KiB
2Elfogadva214ms60088 KiB
subtask220/20
3Elfogadva93ms43016 KiB
4Elfogadva647ms119740 KiB
5Elfogadva538ms99260 KiB
6Elfogadva370ms82280 KiB
7Elfogadva512ms97496 KiB
8Elfogadva360ms80732 KiB
9Elfogadva978ms145256 KiB
subtask30/15
10Futási hiba317ms77204 KiB
11Elfogadva29ms31464 KiB
12Időlimit túllépés1.574s16604 KiB
13Időlimit túllépés1.549s20988 KiB
14Időlimit túllépés1.567s28708 KiB
subtask40/20
15Futási hiba75ms49364 KiB
16Futási hiba303ms82640 KiB
17Elfogadva63ms45240 KiB
18Elfogadva104ms55516 KiB
19Elfogadva50ms40292 KiB
20Elfogadva101ms50296 KiB
subtask50/45
21Időlimit túllépés1.549s15152 KiB
22Elfogadva1.449s202224 KiB
23Elfogadva93ms43988 KiB
24Elfogadva479ms85980 KiB
25Elfogadva411ms84124 KiB
26Elfogadva528ms109804 KiB
27Elfogadva268ms74776 KiB
28Elfogadva1.001s164480 KiB
29Elfogadva197ms60576 KiB
30Elfogadva1.133s156360 KiB
31Futási hiba284ms85284 KiB
32Időlimit túllépés1.582s26116 KiB
33Futási hiba513ms107984 KiB
34Elfogadva412ms84964 KiB
35Elfogadva448ms83068 KiB
36Elfogadva395ms82272 KiB
37Elfogadva523ms81656 KiB