QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#357964#6526. CanvasPorNPtree#WA 3ms32748kbC++173.4kb2024-03-19 15:45:062024-03-19 15:45:07

Judging History

你现在查看的是最新测评结果

  • [2024-03-19 15:45:07]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:32748kb
  • [2024-03-19 15:45:06]
  • 提交

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)