53202023-04-25 21:57:11CattVázsony vonatjegyet vásárolcpp17Runtime error 20/1001.575s194280 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(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
1Accepted12ms27016 KiB
2Accepted199ms63232 KiB
subtask220/20
3Accepted93ms47596 KiB
4Accepted633ms133268 KiB
5Accepted537ms120088 KiB
6Accepted370ms108132 KiB
7Accepted507ms130224 KiB
8Accepted342ms118548 KiB
9Accepted981ms194280 KiB
subtask30/15
10Runtime error303ms130468 KiB
11Accepted30ms84860 KiB
12Time limit exceeded1.557s70376 KiB
13Time limit exceeded1.562s75940 KiB
14Time limit exceeded1.575s85476 KiB
subtask40/20
15Runtime error70ms107084 KiB
16Runtime error305ms142908 KiB
17Accepted61ms105752 KiB
18Accepted107ms117396 KiB
19Accepted52ms102652 KiB
20Accepted104ms113840 KiB
subtask50/45
21Time limit exceeded1.55s79008 KiB
22Time limit exceeded1.554s131736 KiB
23Accepted90ms73528 KiB
24Accepted404ms115572 KiB
25Accepted370ms113620 KiB
26Accepted560ms139300 KiB
27Accepted296ms104280 KiB
28Accepted1.184s193980 KiB
29Accepted196ms90080 KiB
30Accepted930ms185868 KiB
31Runtime error314ms114756 KiB
32Time limit exceeded1.567s55284 KiB
33Runtime error507ms137280 KiB
34Accepted411ms114240 KiB
35Accepted428ms112520 KiB
36Accepted458ms111464 KiB
37Accepted462ms111040 KiB