53312023-04-25 22:31:31CattVázsony vonatjegyet vásárolcpp17Time limit exceeded 55/1001.605s156216 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(s[x] < s[y]) swap(x, y);

    p[y] = x;
    for(ll sz : to[y]) {
        to[x].insert(root(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(int i = 1; i <= n; i++) p[i] = i;
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] == dist[i]) {
                connect(sz.first, i);
            }
        }
    }
    for(ll i = 1; i <= n; i++) {
        for(auto sz : g[i]) {
            if(dist[sz.first] < dist[i]) {
                to[root(i)].insert(root(sz.first));
            }
            else if(dist[sz.first] > dist[i]) {
                to[root(sz.first)].insert(root(i));
            }
        }
    }

    dfs(root(a));
    vector<ll> be(n+1, 0);
    for(ll i = 1; i <= n; i++) {

        if(!volt[i] || root(i) != i) continue;
        for(ll sz : to[i]) be[root(sz)]++;
    }

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

        for(ll sz : to[cur]) {
            be[sz]--;
            if(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 = {root(b)};
    ll cur = root(b);
    while(cur != root(a)) {
        cur = parent[cur];
        mo.insert(root(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
1Accepted12ms26868 KiB
2Accepted216ms59688 KiB
subtask220/20
3Accepted93ms43176 KiB
4Accepted670ms119796 KiB
5Accepted521ms99620 KiB
6Accepted363ms82448 KiB
7Accepted479ms97640 KiB
8Accepted370ms80684 KiB
9Accepted841ms145264 KiB
subtask315/15
10Accepted270ms77088 KiB
11Accepted27ms31404 KiB
12Accepted27ms31476 KiB
13Accepted67ms40080 KiB
14Accepted123ms55424 KiB
subtask420/20
15Accepted82ms48752 KiB
16Accepted272ms63192 KiB
17Accepted57ms45028 KiB
18Accepted96ms55392 KiB
19Accepted52ms40124 KiB
20Accepted96ms47856 KiB
subtask50/45
21Accepted14ms29132 KiB
22Time limit exceeded1.605s96404 KiB
23Accepted86ms43308 KiB
24Accepted400ms83504 KiB
25Accepted340ms73716 KiB
26Accepted588ms98480 KiB
27Accepted307ms75420 KiB
28Accepted1.195s156216 KiB
29Accepted187ms61264 KiB
30Accepted1.115s132352 KiB
31Accepted301ms66056 KiB
32Accepted87ms42704 KiB
33Accepted412ms74464 KiB
34Accepted317ms67772 KiB
35Accepted321ms67768 KiB
36Accepted324ms68140 KiB
37Accepted326ms67976 KiB