53172023-04-25 21:26:12CattVázsony vonatjegyet vásárolcpp17Time limit exceeded 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted14ms26876 KiB
2Time limit exceeded1.6s33364 KiB
subtask20/20
3Time limit exceeded1.557s26432 KiB
4Time limit exceeded1.565s73896 KiB
5Time limit exceeded1.562s71288 KiB
6Time limit exceeded1.569s67884 KiB
7Time limit exceeded1.569s82332 KiB
8Time limit exceeded1.578s79160 KiB
9Time limit exceeded1.572s122932 KiB
subtask30/15
10Time limit exceeded1.58s92960 KiB
11Accepted30ms85492 KiB
12Time limit exceeded1.577s70704 KiB
13Time limit exceeded1.57s76312 KiB
14Time limit exceeded1.559s85784 KiB
subtask40/20
15Time limit exceeded1.523s80288 KiB
16Time limit exceeded1.56s102528 KiB
17Time limit exceeded1.58s81516 KiB
18Time limit exceeded1.526s88228 KiB
19Time limit exceeded1.6s83472 KiB
20Time limit exceeded1.565s89600 KiB
subtask50/45
21Time limit exceeded1.569s79236 KiB
22Time limit exceeded1.575s131752 KiB
23Time limit exceeded1.57s53660 KiB
24Time limit exceeded1.567s79156 KiB
25Time limit exceeded1.562s82700 KiB
26Time limit exceeded1.588s101960 KiB
27Time limit exceeded1.582s88268 KiB
28Time limit exceeded1.569s131732 KiB
29Time limit exceeded1.524s82808 KiB
30Time limit exceeded1.562s131800 KiB
31Time limit exceeded1.557s99608 KiB
32Time limit exceeded1.554s82892 KiB
33Time limit exceeded1.577s116816 KiB
34Time limit exceeded1.534s109000 KiB
35Time limit exceeded1.559s114896 KiB
36Time limit exceeded1.562s120536 KiB
37Time limit exceeded1.577s126136 KiB