| 16268 | 2025-04-19 10:35:12 | szil | Turista járatok | cpp17 | Hibás válasz 20/100 | 158ms | 28668 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 200'001;
vector<pair<int, int>> g[MAXN];
vector<int> bct[MAXN];
vector<pair<int, int>> edges;
vector<int> st;
vector<vector<int>> comps;
bool is_cutpoint[MAXN], is_good[MAXN];
int tin[MAXN], low[MAXN], cid[MAXN], tin2[MAXN], timer = 1, th;
map<int, vector<int>> id_to_nodes;
vector<int> ans;
void dfs(int u, int p = -1) {
int cnt = 0;
tin[u] = low[u] = timer++;
st.emplace_back(u);
for (auto [v, _] : g[u]) {
if (v == p) continue;
if (tin[v]) low[u] = min(low[u], tin[v]);
else {
dfs(v, u);
low[u] = min(low[u], low[v]);
if (low[v] >= tin[u]) {
is_cutpoint[u] = (tin[u] > 1 || tin[v] > 2);
comps.push_back({u});
while (st.back() != u) {
comps.back().push_back(st.back());
st.pop_back();
}
}
}
}
}
void dfs2(int u, int p = -1) {
tin2[u] = timer++;
for (int v : bct[u]) {
if (v != p) {
dfs2(v, u);
}
}
}
void dfs3(int u, int p = -1, bool g = false) {
if (is_good[u]) g = 1;
if (g) {
for (int c : id_to_nodes[u]) ans.emplace_back(c);
}
for (int v : bct[u]) {
if (v != p) dfs3(v, u, g);
}
}
void solve() {
int n, m, k; cin >> n >> m >> k;
for (int i = 0; i < m; i++) {
int u, v; cin >> u >> v;
edges.emplace_back(u, v);
g[u].emplace_back(v, i);
g[v].emplace_back(u, i);
}
dfs(1);
int cc = 0;
for (int i = 1; i <= n; i++) {
if (is_cutpoint[i]) {
cid[i] = ++cc;
id_to_nodes[cc] = {i};
}
}
th = cc;
for (auto &vec : comps) {
int id = ++cc;
sort(vec.begin(), vec.end());
id_to_nodes[id] = {};
for (int u : vec) {
for (auto [v, idx] : g[u]) {
if (idx < k && binary_search(vec.begin(), vec.end(), v)) {
is_good[id] = 1;
}
}
if (is_cutpoint[u]) {
bct[id].emplace_back(cid[u]);
bct[cid[u]].emplace_back(id);
} else {
id_to_nodes[id].emplace_back(u);
cid[u] = id;
}
}
}
dfs2(cid[1]);
for (int i = 0; i < k; i++) {
auto [u, v] = edges[i];
if (tin2[cid[u]] < tin2[cid[v]]) is_good[cid[v]] = 1;
else is_good[cid[u]] = 1;
}
dfs3(cid[1]);
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
cout << ans.size() << "\n";
for (int u : ans) cout << u << " ";
cout << "\n";
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 8ms | 9820 KiB | ||||
| 2 | Elfogadva | 19ms | 11072 KiB | ||||
| subtask2 | 0/10 | ||||||
| 3 | Hibás válasz | 8ms | 9928 KiB | ||||
| 4 | Hibás válasz | 10ms | 9780 KiB | ||||
| 5 | Elfogadva | 10ms | 9780 KiB | ||||
| 6 | Elfogadva | 9ms | 9780 KiB | ||||
| 7 | Hibás válasz | 8ms | 9776 KiB | ||||
| subtask3 | 10/10 | ||||||
| 8 | Elfogadva | 8ms | 9868 KiB | ||||
| 9 | Elfogadva | 8ms | 9780 KiB | ||||
| 10 | Elfogadva | 10ms | 9764 KiB | ||||
| 11 | Elfogadva | 12ms | 10028 KiB | ||||
| 12 | Elfogadva | 16ms | 11264 KiB | ||||
| subtask4 | 10/10 | ||||||
| 13 | Elfogadva | 21ms | 12908 KiB | ||||
| 14 | Elfogadva | 10ms | 9780 KiB | ||||
| 15 | Elfogadva | 10ms | 9780 KiB | ||||
| 16 | Elfogadva | 9ms | 10036 KiB | ||||
| 17 | Elfogadva | 158ms | 28564 KiB | ||||
| 18 | Elfogadva | 56ms | 14588 KiB | ||||
| 19 | Elfogadva | 75ms | 15784 KiB | ||||
| 20 | Elfogadva | 56ms | 14672 KiB | ||||
| subtask5 | 0/10 | ||||||
| 21 | Elfogadva | 17ms | 11060 KiB | ||||
| 22 | Elfogadva | 8ms | 9780 KiB | ||||
| 23 | Hibás válasz | 10ms | 9784 KiB | ||||
| 24 | Elfogadva | 10ms | 9780 KiB | ||||
| 25 | Elfogadva | 94ms | 20388 KiB | ||||
| 26 | Elfogadva | 17ms | 10484 KiB | ||||
| 27 | Elfogadva | 14ms | 10576 KiB | ||||
| subtask6 | 0/60 | ||||||
| 28 | Elfogadva | 8ms | 9780 KiB | ||||
| 29 | Elfogadva | 10ms | 9780 KiB | ||||
| 30 | Elfogadva | 13ms | 10036 KiB | ||||
| 31 | Elfogadva | 10ms | 10036 KiB | ||||
| 32 | Hibás válasz | 12ms | 10348 KiB | ||||
| 33 | Elfogadva | 13ms | 10340 KiB | ||||
| 34 | Elfogadva | 19ms | 10960 KiB | ||||
| 35 | Elfogadva | 20ms | 11164 KiB | ||||
| 36 | Elfogadva | 17ms | 10964 KiB | ||||
| 37 | Elfogadva | 151ms | 28668 KiB | ||||
| 38 | Elfogadva | 59ms | 14656 KiB | ||||
| 39 | Elfogadva | 59ms | 14512 KiB | ||||
| 40 | Elfogadva | 54ms | 14476 KiB | ||||
| 41 | Elfogadva | 61ms | 14500 KiB | ||||
| 42 | Elfogadva | 59ms | 14500 KiB | ||||
| 43 | Elfogadva | 56ms | 14508 KiB | ||||
| 44 | Elfogadva | 56ms | 14576 KiB | ||||
| 45 | Elfogadva | 82ms | 15884 KiB | ||||
| 46 | Elfogadva | 61ms | 14500 KiB | ||||
| 47 | Elfogadva | 57ms | 14480 KiB | ||||
| 48 | Elfogadva | 57ms | 14420 KiB | ||||
| 49 | Elfogadva | 54ms | 14620 KiB | ||||
| 50 | Elfogadva | 57ms | 14516 KiB | ||||