5322 | 2023. 04. 25 22:01:22 | Catt | Vázsony vonatjegyet vásárol | cpp17 | Futási hiba 20/100 | 1.587s | 175920 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[root(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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 10ms | 26868 KiB | ||||
2 | Elfogadva | 212ms | 60204 KiB | ||||
subtask2 | 20/20 | ||||||
3 | Elfogadva | 92ms | 43248 KiB | ||||
4 | Elfogadva | 734ms | 119820 KiB | ||||
5 | Elfogadva | 474ms | 99640 KiB | ||||
6 | Elfogadva | 323ms | 82576 KiB | ||||
7 | Elfogadva | 507ms | 98100 KiB | ||||
8 | Elfogadva | 361ms | 81112 KiB | ||||
9 | Elfogadva | 977ms | 145688 KiB | ||||
subtask3 | 0/15 | ||||||
10 | Futási hiba | 326ms | 81536 KiB | ||||
11 | Elfogadva | 28ms | 35664 KiB | ||||
12 | Időlimit túllépés | 1.557s | 21024 KiB | ||||
13 | Időlimit túllépés | 1.565s | 26288 KiB | ||||
14 | Időlimit túllépés | 1.575s | 35692 KiB | ||||
subtask4 | 0/20 | ||||||
15 | Futási hiba | 76ms | 57112 KiB | ||||
16 | Futási hiba | 305ms | 93500 KiB | ||||
17 | Elfogadva | 57ms | 56084 KiB | ||||
18 | Elfogadva | 104ms | 66480 KiB | ||||
19 | Elfogadva | 54ms | 51296 KiB | ||||
20 | Elfogadva | 94ms | 61556 KiB | ||||
subtask5 | 0/45 | ||||||
21 | Időlimit túllépés | 1.582s | 26436 KiB | ||||
22 | Időlimit túllépés | 1.542s | 113336 KiB | ||||
23 | Elfogadva | 90ms | 55256 KiB | ||||
24 | Elfogadva | 400ms | 97108 KiB | ||||
25 | Elfogadva | 368ms | 95304 KiB | ||||
26 | Elfogadva | 615ms | 121156 KiB | ||||
27 | Elfogadva | 298ms | 86144 KiB | ||||
28 | Elfogadva | 992ms | 175920 KiB | ||||
29 | Elfogadva | 197ms | 71924 KiB | ||||
30 | Elfogadva | 1.136s | 167832 KiB | ||||
31 | Futási hiba | 280ms | 96856 KiB | ||||
32 | Időlimit túllépés | 1.587s | 37356 KiB | ||||
33 | Futási hiba | 504ms | 119432 KiB | ||||
34 | Elfogadva | 486ms | 96260 KiB | ||||
35 | Elfogadva | 397ms | 94308 KiB | ||||
36 | Elfogadva | 507ms | 93260 KiB | ||||
37 | Elfogadva | 513ms | 92740 KiB |