5321 2023. 04. 25 22:00:18 Catt Vázsony vonatjegyet vásárol cpp17 Futási hiba 20/100 1.574s 231872 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]) 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 14ms 26868 KiB
2 Elfogadva 216ms 63144 KiB
subtask2 20/20
3 Elfogadva 92ms 47504 KiB
4 Elfogadva 649ms 133120 KiB
5 Elfogadva 474ms 120260 KiB
6 Elfogadva 375ms 106200 KiB
7 Elfogadva 439ms 121448 KiB
8 Elfogadva 356ms 104500 KiB
9 Elfogadva 968ms 169104 KiB
subtask3 0/15
10 Futási hiba 307ms 105256 KiB
11 Elfogadva 28ms 59360 KiB
12 Időlimit túllépés 1.562s 44792 KiB
13 Időlimit túllépés 1.574s 50292 KiB
14 Időlimit túllépés 1.57s 59940 KiB
subtask4 0/20
15 Futási hiba 70ms 81476 KiB
16 Futási hiba 277ms 117668 KiB
17 Elfogadva 63ms 80272 KiB
18 Elfogadva 93ms 90620 KiB
19 Elfogadva 46ms 75396 KiB
20 Elfogadva 101ms 85504 KiB
subtask5 0/45
21 Időlimit túllépés 1.574s 50380 KiB
22 Elfogadva 1.355s 231872 KiB
23 Elfogadva 85ms 73588 KiB
24 Elfogadva 351ms 115468 KiB
25 Elfogadva 368ms 113640 KiB
26 Elfogadva 611ms 139216 KiB
27 Elfogadva 293ms 104192 KiB
28 Elfogadva 1.101s 193896 KiB
29 Elfogadva 195ms 89896 KiB
30 Elfogadva 1.225s 185676 KiB
31 Futási hiba 279ms 114944 KiB
32 Időlimit túllépés 1.57s 55684 KiB
33 Futási hiba 507ms 137672 KiB
34 Elfogadva 405ms 114644 KiB
35 Elfogadva 442ms 112844 KiB
36 Elfogadva 400ms 111796 KiB
37 Elfogadva 451ms 111272 KiB