5320 2023. 04. 25 21:57:11 Catt Vázsony vonatjegyet vásárol cpp17 Futási hiba 20/100 1.575s 194280 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(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 12ms 27016 KiB
2 Elfogadva 199ms 63232 KiB
subtask2 20/20
3 Elfogadva 93ms 47596 KiB
4 Elfogadva 633ms 133268 KiB
5 Elfogadva 537ms 120088 KiB
6 Elfogadva 370ms 108132 KiB
7 Elfogadva 507ms 130224 KiB
8 Elfogadva 342ms 118548 KiB
9 Elfogadva 981ms 194280 KiB
subtask3 0/15
10 Futási hiba 303ms 130468 KiB
11 Elfogadva 30ms 84860 KiB
12 Időlimit túllépés 1.557s 70376 KiB
13 Időlimit túllépés 1.562s 75940 KiB
14 Időlimit túllépés 1.575s 85476 KiB
subtask4 0/20
15 Futási hiba 70ms 107084 KiB
16 Futási hiba 305ms 142908 KiB
17 Elfogadva 61ms 105752 KiB
18 Elfogadva 107ms 117396 KiB
19 Elfogadva 52ms 102652 KiB
20 Elfogadva 104ms 113840 KiB
subtask5 0/45
21 Időlimit túllépés 1.55s 79008 KiB
22 Időlimit túllépés 1.554s 131736 KiB
23 Elfogadva 90ms 73528 KiB
24 Elfogadva 404ms 115572 KiB
25 Elfogadva 370ms 113620 KiB
26 Elfogadva 560ms 139300 KiB
27 Elfogadva 296ms 104280 KiB
28 Elfogadva 1.184s 193980 KiB
29 Elfogadva 196ms 90080 KiB
30 Elfogadva 930ms 185868 KiB
31 Futási hiba 314ms 114756 KiB
32 Időlimit túllépés 1.567s 55284 KiB
33 Futási hiba 507ms 137280 KiB
34 Elfogadva 411ms 114240 KiB
35 Elfogadva 428ms 112520 KiB
36 Elfogadva 458ms 111464 KiB
37 Elfogadva 462ms 111040 KiB