5323 2023. 04. 25 22:02:54 Catt Vázsony vonatjegyet vásárol cpp17 Futási hiba 20/100 1.582s 202224 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 13ms 26868 KiB
2 Elfogadva 214ms 60088 KiB
subtask2 20/20
3 Elfogadva 93ms 43016 KiB
4 Elfogadva 647ms 119740 KiB
5 Elfogadva 538ms 99260 KiB
6 Elfogadva 370ms 82280 KiB
7 Elfogadva 512ms 97496 KiB
8 Elfogadva 360ms 80732 KiB
9 Elfogadva 978ms 145256 KiB
subtask3 0/15
10 Futási hiba 317ms 77204 KiB
11 Elfogadva 29ms 31464 KiB
12 Időlimit túllépés 1.574s 16604 KiB
13 Időlimit túllépés 1.549s 20988 KiB
14 Időlimit túllépés 1.567s 28708 KiB
subtask4 0/20
15 Futási hiba 75ms 49364 KiB
16 Futási hiba 303ms 82640 KiB
17 Elfogadva 63ms 45240 KiB
18 Elfogadva 104ms 55516 KiB
19 Elfogadva 50ms 40292 KiB
20 Elfogadva 101ms 50296 KiB
subtask5 0/45
21 Időlimit túllépés 1.549s 15152 KiB
22 Elfogadva 1.449s 202224 KiB
23 Elfogadva 93ms 43988 KiB
24 Elfogadva 479ms 85980 KiB
25 Elfogadva 411ms 84124 KiB
26 Elfogadva 528ms 109804 KiB
27 Elfogadva 268ms 74776 KiB
28 Elfogadva 1.001s 164480 KiB
29 Elfogadva 197ms 60576 KiB
30 Elfogadva 1.133s 156360 KiB
31 Futási hiba 284ms 85284 KiB
32 Időlimit túllépés 1.582s 26116 KiB
33 Futási hiba 513ms 107984 KiB
34 Elfogadva 412ms 84964 KiB
35 Elfogadva 448ms 83068 KiB
36 Elfogadva 395ms 82272 KiB
37 Elfogadva 523ms 81656 KiB