QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#384656 | #4498. Planar Graph | Tobo# | WA | 259ms | 6296kb | C++17 | 1001b | 2024-04-10 08:46:17 | 2024-04-10 08:46:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--)
{
int n, m;
cin >> n >> m;
vector<array<int, 2>> e(m);
for (auto &[u, v] : e)
cin >> u >> v;
vector<int> vis(m), fa(n + 1);
iota(fa.begin(), fa.end(), 0);
auto find = [&](auto &find, int x)
{
if (x == fa[x])
return x;
return fa[x] = find(find, fa[x]);
};
for (int i = m - 1; i >= 0; i--)
{
auto [u, v] = e[i];
int fx = find(find, u), fy = find(find, v);
if (fx == fy)
vis[i] = 1;
else
fa[fx] = fy;
}
cout << m - n + 1 << '\n';
for (int i = 0; i < m; i++)
if (vis[i])
cout << i + 1 << ' ';
cout << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 259ms
memory: 6296kb
input:
15 5 7 1 1 1 2 1 3 3 4 3 4 2 4 2 5 9 9 1 2 2 3 3 1 4 5 5 6 6 4 7 8 8 9 9 7 100000 0 100000 200000 77128 77528 77919 78319 67747 68147 21468 21468 9500 9500 3099 3099 60221 60222 71712 71713 26587 93317 6972 6972 58270 58271 7190 7190 76105 76106 73929 74329 32751 32751 4 5 35248 35648 4492 96872 160...
output:
3 1 2 4 1 1 4 7 -99999 100001 1 2 3 4 5 6 7 8 10 11 12 13 14 15 16 17 19 20 21 22 23 26 27 28 29 30 31 33 34 36 39 40 41 42 43 45 46 47 48 52 53 55 56 57 58 59 61 62 63 65 66 68 69 72 73 74 75 77 78 79 80 83 84 85 86 87 88 89 90 91 92 93 94 95 96 98 100 101 103 105 106 107 108 109 110 111 113 114...
result:
wrong answer 3rd lines differ - expected: '3', found: '1'