| 16270 | 2025-04-19 10:43:39 | szil | Turista járatok | cpp17 | Hibás válasz 30/100 | 180ms | 42748 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 500'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]) {
if (c != 1) 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 | 18ms | 23860 KiB | ||||
| 2 | Elfogadva | 34ms | 25140 KiB | ||||
| subtask2 | 10/10 | ||||||
| 3 | Elfogadva | 25ms | 23860 KiB | ||||
| 4 | Elfogadva | 19ms | 23948 KiB | ||||
| 5 | Elfogadva | 26ms | 23864 KiB | ||||
| 6 | Elfogadva | 19ms | 23860 KiB | ||||
| 7 | Elfogadva | 18ms | 23860 KiB | ||||
| subtask3 | 10/10 | ||||||
| 8 | Elfogadva | 25ms | 23860 KiB | ||||
| 9 | Elfogadva | 19ms | 23872 KiB | ||||
| 10 | Elfogadva | 19ms | 23816 KiB | ||||
| 11 | Elfogadva | 26ms | 24116 KiB | ||||
| 12 | Elfogadva | 26ms | 25396 KiB | ||||
| subtask4 | 10/10 | ||||||
| 13 | Elfogadva | 39ms | 26992 KiB | ||||
| 14 | Elfogadva | 19ms | 23860 KiB | ||||
| 15 | Elfogadva | 25ms | 23860 KiB | ||||
| 16 | Elfogadva | 20ms | 24140 KiB | ||||
| 17 | Elfogadva | 173ms | 42644 KiB | ||||
| 18 | Elfogadva | 74ms | 28580 KiB | ||||
| 19 | Elfogadva | 83ms | 29860 KiB | ||||
| 20 | Elfogadva | 68ms | 28536 KiB | ||||
| subtask5 | 0/10 | ||||||
| 21 | Elfogadva | 35ms | 25140 KiB | ||||
| 22 | Elfogadva | 19ms | 23860 KiB | ||||
| 23 | Hibás válasz | 20ms | 23860 KiB | ||||
| 24 | Elfogadva | 25ms | 23872 KiB | ||||
| 25 | Elfogadva | 108ms | 34360 KiB | ||||
| 26 | Elfogadva | 26ms | 24640 KiB | ||||
| 27 | Elfogadva | 26ms | 24632 KiB | ||||
| subtask6 | 0/60 | ||||||
| 28 | Elfogadva | 20ms | 23860 KiB | ||||
| 29 | Elfogadva | 20ms | 23860 KiB | ||||
| 30 | Elfogadva | 27ms | 24116 KiB | ||||
| 31 | Elfogadva | 28ms | 24116 KiB | ||||
| 32 | Hibás válasz | 23ms | 24372 KiB | ||||
| 33 | Elfogadva | 24ms | 24372 KiB | ||||
| 34 | Elfogadva | 28ms | 25136 KiB | ||||
| 35 | Elfogadva | 34ms | 25296 KiB | ||||
| 36 | Elfogadva | 28ms | 25140 KiB | ||||
| 37 | Elfogadva | 180ms | 42748 KiB | ||||
| 38 | Elfogadva | 74ms | 28736 KiB | ||||
| 39 | Elfogadva | 67ms | 28576 KiB | ||||
| 40 | Elfogadva | 67ms | 28840 KiB | ||||
| 41 | Elfogadva | 67ms | 28736 KiB | ||||
| 42 | Elfogadva | 76ms | 28584 KiB | ||||
| 43 | Elfogadva | 67ms | 28584 KiB | ||||
| 44 | Elfogadva | 75ms | 28584 KiB | ||||
| 45 | Elfogadva | 94ms | 29860 KiB | ||||
| 46 | Elfogadva | 67ms | 28580 KiB | ||||
| 47 | Elfogadva | 67ms | 28584 KiB | ||||
| 48 | Elfogadva | 67ms | 28688 KiB | ||||
| 49 | Elfogadva | 72ms | 28596 KiB | ||||
| 50 | Elfogadva | 65ms | 28756 KiB | ||||