5330 2023. 04. 25 22:29:09 Catt Vázsony vonatjegyet vásárol cpp17 Időlimit túllépés 55/100 1.567s 156084 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(root(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(int i = 1; i <= n; i++) p[i] = i;
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] == dist[i]) {
                connect(sz.first, i);
            }
        }
    }
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] < dist[i]) {
                to[root(i)].insert(root(sz.first));
            }
            else if(dist[sz.first] > dist[i]) {
                to[root(sz.first)].insert(root(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);
    
    tav[root(a)] = 0;
    queue<ll> sor;
    sor.push(root(a));
    while(!sor.empty()) {
        ll cur = sor.front();
        sor.pop();

        for(ll sz : to[cur]) {
            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 14ms 26868 KiB
2 Elfogadva 201ms 59660 KiB
subtask2 20/20
3 Elfogadva 87ms 43160 KiB
4 Elfogadva 759ms 119800 KiB
5 Elfogadva 551ms 99492 KiB
6 Elfogadva 379ms 82336 KiB
7 Elfogadva 556ms 97800 KiB
8 Elfogadva 368ms 80784 KiB
9 Elfogadva 1.049s 145388 KiB
subtask3 15/15
10 Elfogadva 280ms 77448 KiB
11 Elfogadva 29ms 31676 KiB
12 Elfogadva 25ms 31580 KiB
13 Elfogadva 64ms 40452 KiB
14 Elfogadva 123ms 55724 KiB
subtask4 20/20
15 Elfogadva 92ms 49216 KiB
16 Elfogadva 250ms 63476 KiB
17 Elfogadva 63ms 45284 KiB
18 Elfogadva 97ms 55640 KiB
19 Elfogadva 50ms 40116 KiB
20 Elfogadva 94ms 48172 KiB
subtask5 0/45
21 Elfogadva 12ms 29152 KiB
22 Időlimit túllépés 1.567s 96692 KiB
23 Elfogadva 90ms 43384 KiB
24 Elfogadva 397ms 83504 KiB
25 Elfogadva 312ms 73740 KiB
26 Elfogadva 587ms 98408 KiB
27 Elfogadva 305ms 75448 KiB
28 Elfogadva 1.2s 156084 KiB
29 Elfogadva 197ms 61144 KiB
30 Elfogadva 1.095s 132140 KiB
31 Elfogadva 303ms 65840 KiB
32 Elfogadva 85ms 42608 KiB
33 Elfogadva 382ms 74516 KiB
34 Elfogadva 321ms 67788 KiB
35 Elfogadva 321ms 67776 KiB
36 Elfogadva 301ms 67768 KiB
37 Elfogadva 326ms 67772 KiB