53222023-04-25 22:01:22CattVázsony vonatjegyet vásárolcpp17Futási hiba 20/1001.587s175920 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ÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva10ms26868 KiB
2Elfogadva212ms60204 KiB
subtask220/20
3Elfogadva92ms43248 KiB
4Elfogadva734ms119820 KiB
5Elfogadva474ms99640 KiB
6Elfogadva323ms82576 KiB
7Elfogadva507ms98100 KiB
8Elfogadva361ms81112 KiB
9Elfogadva977ms145688 KiB
subtask30/15
10Futási hiba326ms81536 KiB
11Elfogadva28ms35664 KiB
12Időlimit túllépés1.557s21024 KiB
13Időlimit túllépés1.565s26288 KiB
14Időlimit túllépés1.575s35692 KiB
subtask40/20
15Futási hiba76ms57112 KiB
16Futási hiba305ms93500 KiB
17Elfogadva57ms56084 KiB
18Elfogadva104ms66480 KiB
19Elfogadva54ms51296 KiB
20Elfogadva94ms61556 KiB
subtask50/45
21Időlimit túllépés1.582s26436 KiB
22Időlimit túllépés1.542s113336 KiB
23Elfogadva90ms55256 KiB
24Elfogadva400ms97108 KiB
25Elfogadva368ms95304 KiB
26Elfogadva615ms121156 KiB
27Elfogadva298ms86144 KiB
28Elfogadva992ms175920 KiB
29Elfogadva197ms71924 KiB
30Elfogadva1.136s167832 KiB
31Futási hiba280ms96856 KiB
32Időlimit túllépés1.587s37356 KiB
33Futási hiba504ms119432 KiB
34Elfogadva486ms96260 KiB
35Elfogadva397ms94308 KiB
36Elfogadva507ms93260 KiB
37Elfogadva513ms92740 KiB