53272023-04-25 22:21:21CattVázsony vonatjegyet vásárolcpp17Hibás válasz 20/1001.572s164952 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva14ms26872 KiB
2Elfogadva216ms60176 KiB
subtask220/20
3Elfogadva101ms43160 KiB
4Elfogadva811ms119884 KiB
5Elfogadva550ms99628 KiB
6Elfogadva379ms82588 KiB
7Elfogadva523ms97848 KiB
8Elfogadva365ms80900 KiB
9Elfogadva998ms145500 KiB
subtask30/15
10Hibás válasz314ms77560 KiB
11Elfogadva29ms31716 KiB
12Hibás válasz28ms31736 KiB
13Hibás válasz71ms40736 KiB
14Hibás válasz178ms55700 KiB
subtask40/20
15Futási hiba83ms47620 KiB
16Futási hiba272ms80248 KiB
17Futási hiba46ms43180 KiB
18Futási hiba86ms53932 KiB
19Futási hiba43ms41116 KiB
20Futási hiba82ms50996 KiB
subtask50/45
21Futási hiba13ms29352 KiB
22Időlimit túllépés1.572s102632 KiB
23Hibás válasz87ms44520 KiB
24Hibás válasz363ms86388 KiB
25Hibás válasz358ms84456 KiB
26Hibás válasz624ms110136 KiB
27Elfogadva275ms75388 KiB
28Hibás válasz1.008s164952 KiB
29Hibás válasz187ms61156 KiB
30Hibás válasz931ms156676 KiB
31Elfogadva331ms83752 KiB
32Hibás válasz122ms48768 KiB
33Hibás válasz513ms104384 KiB
34Futási hiba388ms82064 KiB
35Futási hiba386ms82008 KiB
36Futási hiba388ms82012 KiB
37Futási hiba400ms82052 KiB