53272023-04-25 22:21:21CattVázsony vonatjegyet vásárolcpp17Wrong answer 20/1001.572s164952 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(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(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] || 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]) {
            if(sz != root(sz) && to[cur].find(root(sz)) != to[cur].end()) continue;
            sz = root(sz);
            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
1Accepted14ms26872 KiB
2Accepted216ms60176 KiB
subtask220/20
3Accepted101ms43160 KiB
4Accepted811ms119884 KiB
5Accepted550ms99628 KiB
6Accepted379ms82588 KiB
7Accepted523ms97848 KiB
8Accepted365ms80900 KiB
9Accepted998ms145500 KiB
subtask30/15
10Wrong answer314ms77560 KiB
11Accepted29ms31716 KiB
12Wrong answer28ms31736 KiB
13Wrong answer71ms40736 KiB
14Wrong answer178ms55700 KiB
subtask40/20
15Runtime error83ms47620 KiB
16Runtime error272ms80248 KiB
17Runtime error46ms43180 KiB
18Runtime error86ms53932 KiB
19Runtime error43ms41116 KiB
20Runtime error82ms50996 KiB
subtask50/45
21Runtime error13ms29352 KiB
22Time limit exceeded1.572s102632 KiB
23Wrong answer87ms44520 KiB
24Wrong answer363ms86388 KiB
25Wrong answer358ms84456 KiB
26Wrong answer624ms110136 KiB
27Accepted275ms75388 KiB
28Wrong answer1.008s164952 KiB
29Wrong answer187ms61156 KiB
30Wrong answer931ms156676 KiB
31Accepted331ms83752 KiB
32Wrong answer122ms48768 KiB
33Wrong answer513ms104384 KiB
34Runtime error388ms82064 KiB
35Runtime error386ms82008 KiB
36Runtime error388ms82012 KiB
37Runtime error400ms82052 KiB