53212023-04-25 22:00:18CattVázsony vonatjegyet vásárolcpp17Runtime error 20/1001.574s231872 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[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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted14ms26868 KiB
2Accepted216ms63144 KiB
subtask220/20
3Accepted92ms47504 KiB
4Accepted649ms133120 KiB
5Accepted474ms120260 KiB
6Accepted375ms106200 KiB
7Accepted439ms121448 KiB
8Accepted356ms104500 KiB
9Accepted968ms169104 KiB
subtask30/15
10Runtime error307ms105256 KiB
11Accepted28ms59360 KiB
12Time limit exceeded1.562s44792 KiB
13Time limit exceeded1.574s50292 KiB
14Time limit exceeded1.57s59940 KiB
subtask40/20
15Runtime error70ms81476 KiB
16Runtime error277ms117668 KiB
17Accepted63ms80272 KiB
18Accepted93ms90620 KiB
19Accepted46ms75396 KiB
20Accepted101ms85504 KiB
subtask50/45
21Time limit exceeded1.574s50380 KiB
22Accepted1.355s231872 KiB
23Accepted85ms73588 KiB
24Accepted351ms115468 KiB
25Accepted368ms113640 KiB
26Accepted611ms139216 KiB
27Accepted293ms104192 KiB
28Accepted1.101s193896 KiB
29Accepted195ms89896 KiB
30Accepted1.225s185676 KiB
31Runtime error279ms114944 KiB
32Time limit exceeded1.57s55684 KiB
33Runtime error507ms137672 KiB
34Accepted405ms114644 KiB
35Accepted442ms112844 KiB
36Accepted400ms111796 KiB
37Accepted451ms111272 KiB