5322 2023. 04. 25 22:01:22 Catt Vázsony vonatjegyet vásárol cpp17 Futási hiba 20/100 1.587s 175920 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[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 10ms 26868 KiB
2 Elfogadva 212ms 60204 KiB
subtask2 20/20
3 Elfogadva 92ms 43248 KiB
4 Elfogadva 734ms 119820 KiB
5 Elfogadva 474ms 99640 KiB
6 Elfogadva 323ms 82576 KiB
7 Elfogadva 507ms 98100 KiB
8 Elfogadva 361ms 81112 KiB
9 Elfogadva 977ms 145688 KiB
subtask3 0/15
10 Futási hiba 326ms 81536 KiB
11 Elfogadva 28ms 35664 KiB
12 Időlimit túllépés 1.557s 21024 KiB
13 Időlimit túllépés 1.565s 26288 KiB
14 Időlimit túllépés 1.575s 35692 KiB
subtask4 0/20
15 Futási hiba 76ms 57112 KiB
16 Futási hiba 305ms 93500 KiB
17 Elfogadva 57ms 56084 KiB
18 Elfogadva 104ms 66480 KiB
19 Elfogadva 54ms 51296 KiB
20 Elfogadva 94ms 61556 KiB
subtask5 0/45
21 Időlimit túllépés 1.582s 26436 KiB
22 Időlimit túllépés 1.542s 113336 KiB
23 Elfogadva 90ms 55256 KiB
24 Elfogadva 400ms 97108 KiB
25 Elfogadva 368ms 95304 KiB
26 Elfogadva 615ms 121156 KiB
27 Elfogadva 298ms 86144 KiB
28 Elfogadva 992ms 175920 KiB
29 Elfogadva 197ms 71924 KiB
30 Elfogadva 1.136s 167832 KiB
31 Futási hiba 280ms 96856 KiB
32 Időlimit túllépés 1.587s 37356 KiB
33 Futási hiba 504ms 119432 KiB
34 Elfogadva 486ms 96260 KiB
35 Elfogadva 397ms 94308 KiB
36 Elfogadva 507ms 93260 KiB
37 Elfogadva 513ms 92740 KiB