53302023-04-25 22:29:09CattVázsony vonatjegyet vásárolcpp17Időlimit túllépés 55/1001.567s156084 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(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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva14ms26868 KiB
2Elfogadva201ms59660 KiB
subtask220/20
3Elfogadva87ms43160 KiB
4Elfogadva759ms119800 KiB
5Elfogadva551ms99492 KiB
6Elfogadva379ms82336 KiB
7Elfogadva556ms97800 KiB
8Elfogadva368ms80784 KiB
9Elfogadva1.049s145388 KiB
subtask315/15
10Elfogadva280ms77448 KiB
11Elfogadva29ms31676 KiB
12Elfogadva25ms31580 KiB
13Elfogadva64ms40452 KiB
14Elfogadva123ms55724 KiB
subtask420/20
15Elfogadva92ms49216 KiB
16Elfogadva250ms63476 KiB
17Elfogadva63ms45284 KiB
18Elfogadva97ms55640 KiB
19Elfogadva50ms40116 KiB
20Elfogadva94ms48172 KiB
subtask50/45
21Elfogadva12ms29152 KiB
22Időlimit túllépés1.567s96692 KiB
23Elfogadva90ms43384 KiB
24Elfogadva397ms83504 KiB
25Elfogadva312ms73740 KiB
26Elfogadva587ms98408 KiB
27Elfogadva305ms75448 KiB
28Elfogadva1.2s156084 KiB
29Elfogadva197ms61144 KiB
30Elfogadva1.095s132140 KiB
31Elfogadva303ms65840 KiB
32Elfogadva85ms42608 KiB
33Elfogadva382ms74516 KiB
34Elfogadva321ms67788 KiB
35Elfogadva321ms67776 KiB
36Elfogadva301ms67768 KiB
37Elfogadva326ms67772 KiB