5326 2023. 04. 25 22:07:35 Catt Vázsony vonatjegyet vásárol cpp17 Időlimit túllépés 55/100 1.605s 165484 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 = {root(b)};
    ll cur = root(b);
    while(cur != root(a)) {
        cur = parent[cur];
        mo.insert(root(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 12ms 26904 KiB
2 Elfogadva 215ms 60236 KiB
subtask2 20/20
3 Elfogadva 93ms 42960 KiB
4 Elfogadva 740ms 119508 KiB
5 Elfogadva 537ms 98996 KiB
6 Elfogadva 344ms 81860 KiB
7 Elfogadva 507ms 97328 KiB
8 Elfogadva 319ms 80560 KiB
9 Elfogadva 824ms 145144 KiB
subtask3 15/15
10 Elfogadva 307ms 77184 KiB
11 Elfogadva 29ms 31552 KiB
12 Elfogadva 26ms 31660 KiB
13 Elfogadva 67ms 40252 KiB
14 Elfogadva 162ms 55560 KiB
subtask4 20/20
15 Elfogadva 100ms 50604 KiB
16 Elfogadva 405ms 84392 KiB
17 Elfogadva 59ms 45424 KiB
18 Elfogadva 107ms 55920 KiB
19 Elfogadva 48ms 40732 KiB
20 Elfogadva 104ms 50968 KiB
subtask5 0/45
21 Elfogadva 14ms 29180 KiB
22 Időlimit túllépés 1.605s 102956 KiB
23 Elfogadva 90ms 44880 KiB
24 Elfogadva 400ms 86660 KiB
25 Elfogadva 372ms 84836 KiB
26 Elfogadva 523ms 110588 KiB
27 Elfogadva 268ms 75696 KiB
28 Elfogadva 994ms 165484 KiB
29 Elfogadva 199ms 61328 KiB
30 Elfogadva 1.136s 157264 KiB
31 Elfogadva 333ms 86248 KiB
32 Elfogadva 122ms 50624 KiB
33 Elfogadva 532ms 110236 KiB
34 Elfogadva 407ms 85824 KiB
35 Elfogadva 446ms 83876 KiB
36 Elfogadva 442ms 82844 KiB
37 Elfogadva 460ms 82192 KiB