5327 2023. 04. 25 22:21:21 Catt Vázsony vonatjegyet vásárol cpp17 Hibás válasz 20/100 1.572s 164952 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(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);
    
    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]) {
            if(sz != root(sz) && to[cur].find(root(sz)) != to[cur].end()) continue;
            sz = root(sz);
            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 26872 KiB
2 Elfogadva 216ms 60176 KiB
subtask2 20/20
3 Elfogadva 101ms 43160 KiB
4 Elfogadva 811ms 119884 KiB
5 Elfogadva 550ms 99628 KiB
6 Elfogadva 379ms 82588 KiB
7 Elfogadva 523ms 97848 KiB
8 Elfogadva 365ms 80900 KiB
9 Elfogadva 998ms 145500 KiB
subtask3 0/15
10 Hibás válasz 314ms 77560 KiB
11 Elfogadva 29ms 31716 KiB
12 Hibás válasz 28ms 31736 KiB
13 Hibás válasz 71ms 40736 KiB
14 Hibás válasz 178ms 55700 KiB
subtask4 0/20
15 Futási hiba 83ms 47620 KiB
16 Futási hiba 272ms 80248 KiB
17 Futási hiba 46ms 43180 KiB
18 Futási hiba 86ms 53932 KiB
19 Futási hiba 43ms 41116 KiB
20 Futási hiba 82ms 50996 KiB
subtask5 0/45
21 Futási hiba 13ms 29352 KiB
22 Időlimit túllépés 1.572s 102632 KiB
23 Hibás válasz 87ms 44520 KiB
24 Hibás válasz 363ms 86388 KiB
25 Hibás válasz 358ms 84456 KiB
26 Hibás válasz 624ms 110136 KiB
27 Elfogadva 275ms 75388 KiB
28 Hibás válasz 1.008s 164952 KiB
29 Hibás válasz 187ms 61156 KiB
30 Hibás válasz 931ms 156676 KiB
31 Elfogadva 331ms 83752 KiB
32 Hibás válasz 122ms 48768 KiB
33 Hibás válasz 513ms 104384 KiB
34 Futási hiba 388ms 82064 KiB
35 Futási hiba 386ms 82008 KiB
36 Futási hiba 388ms 82012 KiB
37 Futási hiba 400ms 82052 KiB