QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#357964 | #6526. Canvas | PorNPtree# | WA | 3ms | 32748kb | C++17 | 3.4kb | 2024-03-19 15:45:06 | 2024-03-19 15:45:07 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
pair<int, int> E[N];
int a[N], b[N], vs[N];
vector< pair<int, int> > G[N];
vector<int> z;
void dfs(int x)
{
for (auto [v, w] : G[x]) {
if (!vs[w]) {
z.push_back(w);
vs[w] = 1;
}
if (a[v] != 2) {
a[v] = 2;
dfs(v);
}
}
return;
}
void dfs2(int x)
{
for (auto [v, w] : G[x]) {
if (!vs[w]) {
z.push_back(w);
vs[w] = 1;
dfs2(v);
}
}
return;
}
int dfn[N], low[N], inS[N], wh[N], du[N], id[N];
stack<int> S;
void tj(int x)
{
dfn[x] = low[x] = ++dfn[0];
inS[x] = 1;
S.push(x);
for (auto [v, w] : G[x]) {
if (!dfn[v]) {
tj(v);
low[x] = min(low[x], low[v]);
} else if (inS[v]) {
low[x] = min(low[x], dfn[v]);
}
}
if (dfn[x] == low[x]) {
int v;
++wh[0];
id[wh[0]] = x;
do {
v = S.top();
S.pop();
inS[v] = 0;
wh[v] = wh[0];
} while (v != x);
}
return;
}
signed main()
{
int T;
scanf("%d", &T);
while (T--) {
int n, m, q = 0;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
a[i] = b[i] = 0;
G[i].clear();
}
z.clear();
vector<int> tz;
for (int i = 1; i <= m; ++i) {
vs[i] = 0;
int l, x, r, y;
scanf("%d%d%d%d", &l, &x, &r, &y);
if (x == 1 && y == 1) {
a[l] = a[r] = 1;
tz.push_back(i);
} else if (x == 2 && y == 2) {
b[x] = b[y] = 1;
z.push_back(i);
} else {
E[++q] = make_pair((x == 1 ? l : r), (y == 1 ? l : r));
G[x].push_back(make_pair(y, i));
a[l] = a[r] = 1;
}
}
for (int i = 1; i <= n; ++i) {
if (b[i]) {
a[i] = 2;
}
}
for (int i = 1; i <= n; ++i) {
if (a[i] == 2) {
dfs(i);
}
}
int res = 0;
for (int i = 1; i <= n; ++i) {
res += a[i];
G[i].clear();
dfn[i] = low[i] = 0;
}
for (int i = 1; i <= q; ++i) {
if (a[E[i].first] == 1 && a[E[i].second] == 1) {
G[E[i].first].push_back(make_pair(E[i].second, i));
}
}
dfn[0] = wh[0] = 0;
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) {
tj(i);
}
}
for (int i = 1; i <= wh[0]; ++i) {
du[i] = 0;
}
for (int i = 1; i <= q; ++i) {
if (a[E[i].first] == 1 && a[E[i].second] == 1 && wh[E[i].first] != wh[E[i].second]) {
++du[wh[E[i].second]];
}
}
res += n;
for (int i = 1; i <= wh[0]; ++i) {
if (!du[wh[i]]) {
--res;
dfs2(id[i]);
}
}
for (int i = 0; i < (int)tz.size(); ++i) {
z.push_back(tz[i]);
}
printf("%d\n", res);
for (int i = m - 1; ~i; --i) {
printf("%d%c", z[i], " \n"[!i]);
}
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 32552kb
input:
2 4 4 1 1 2 2 3 2 4 1 1 2 3 2 2 1 4 1 4 2 3 2 4 1 1 2 3 1
output:
7 4 1 2 3 5 2 1
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 32748kb
input:
1 10 13 1 1 2 2 2 1 3 2 1 2 3 1 3 1 4 2 4 1 5 2 5 1 6 2 4 2 6 1 7 1 8 2 8 1 9 2 7 2 9 1 5 2 9 1 8 2 10 2 1 1 10 1
output:
19 13 11 10 7 9 8 6 5 4 2 1 3 12
result:
wrong answer Participant's solution is incorrect. (test case 1)