53172023-04-25 21:26:12CattVázsony vonatjegyet vásárolcpp17Időlimit túllépés 0/1001.6s131800 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);

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});
        }
    }
}

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);
            }
        }
    }
    vector<ll> be(n+1, 0);
    for(ll i = 1; i <= n; i++) {
        for(ll sz : to[i]) be[root(sz)]++;
    }

    vector<ll> tav(n+1, -1), parent(n+1, -1);
    queue<ll> sor;
    sor.push(root(a));
    while(!sor.empty()) {
        ll cur = sor.front();
        sor.pop();

        for(ll sz : to[cur]) {
            sz = root(sz);
            be[sz]--;
            if((tav[sz] == tav[cur] + 1 && s[cur] > s[p[sz]]) || tav[sz] < tav[cur] + 1) {
                tav[sz] = tav[cur] + 1;
                p[sz] = cur;
            }
            tav[sz] = max(tav[sz], tav[cur] + 1);

            if(be[sz] == 0) {
                sor.push(sz);
            }
        }
    }

    set<ll> mo = {b};
    ll cur = b;
    while(cur != a) {
        cur = p[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
1Elfogadva14ms26876 KiB
2Időlimit túllépés1.6s33364 KiB
subtask20/20
3Időlimit túllépés1.557s26432 KiB
4Időlimit túllépés1.565s73896 KiB
5Időlimit túllépés1.562s71288 KiB
6Időlimit túllépés1.569s67884 KiB
7Időlimit túllépés1.569s82332 KiB
8Időlimit túllépés1.578s79160 KiB
9Időlimit túllépés1.572s122932 KiB
subtask30/15
10Időlimit túllépés1.58s92960 KiB
11Elfogadva30ms85492 KiB
12Időlimit túllépés1.577s70704 KiB
13Időlimit túllépés1.57s76312 KiB
14Időlimit túllépés1.559s85784 KiB
subtask40/20
15Időlimit túllépés1.523s80288 KiB
16Időlimit túllépés1.56s102528 KiB
17Időlimit túllépés1.58s81516 KiB
18Időlimit túllépés1.526s88228 KiB
19Időlimit túllépés1.6s83472 KiB
20Időlimit túllépés1.565s89600 KiB
subtask50/45
21Időlimit túllépés1.569s79236 KiB
22Időlimit túllépés1.575s131752 KiB
23Időlimit túllépés1.57s53660 KiB
24Időlimit túllépés1.567s79156 KiB
25Időlimit túllépés1.562s82700 KiB
26Időlimit túllépés1.588s101960 KiB
27Időlimit túllépés1.582s88268 KiB
28Időlimit túllépés1.569s131732 KiB
29Időlimit túllépés1.524s82808 KiB
30Időlimit túllépés1.562s131800 KiB
31Időlimit túllépés1.557s99608 KiB
32Időlimit túllépés1.554s82892 KiB
33Időlimit túllépés1.577s116816 KiB
34Időlimit túllépés1.534s109000 KiB
35Időlimit túllépés1.559s114896 KiB
36Időlimit túllépés1.562s120536 KiB
37Időlimit túllépés1.577s126136 KiB