QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#179703#6414. Classical Maximization ProblemCurious_DroidWA 0ms7540kbC++233.1kb2023-09-15 02:03:122023-09-15 02:03:12

Judging History

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

  • [2023-09-15 02:03:12]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:7540kb
  • [2023-09-15 02:03:12]
  • 提交

answer

#include <iostream>
#include <vector>
#include <algorithm>

int n, a[100001], b[100001];
std::pair<int, int> p[100001];

int tin[100001];
bool used[100001];

std::vector<std::pair<int, int>> g[100001];
std::vector<std::pair<int, int>> ans;

int timer = 0;

void dfs(int u, int prev)
{
    timer++;
    tin[u] = timer;
    int curr = -1;
    for (auto pr : g[u])
    {
        int v = pr.first;
        int next = pr.second;
        if (!tin[v])
        {
            dfs(v, next);
        }
        if (!used[next] && tin[v] > tin[u])
        {
            if (curr != -1)
            {
                ans.push_back({curr, next});
                used[curr] = used[next] = true;
                curr = -1;
            }
            else
            {
                curr = next;
            }
        }
    }
    if (curr != -1 && prev != -1)
    {
        ans.push_back({curr, prev});
        used[curr] = used[prev] = true;
    }
}

signed main()
{
    int t;
    std::cin >> t;
    while (t--)
    {
        std::cin >> n;
        n *= 2;
        for (int i = 1; i <= n; i++)
        {
            std::cin >> p[i].first >> p[i].second;
        }

        int numa = 0, numb = 0;
        for (int i = 1; i <= n; i++)
        {
            numa++;
            a[numa] = p[i].first;
        }
        std::sort(a + 1, a + 1 + numa), numa = std::unique(a + 1, a + 1 + numa) - a - 1;
        numb = 0;
        for (int i = 1; i <= n; i++)
        {
            numb++;
            b[numb] = p[i].second;
        }
        std::sort(b + 1, b + 1 + numb), numb = std::unique(b + 1, b + 1 + numb) - b - 1;

        for (int i = 1; i <= n; i++)
        {
            p[i].first = std::lower_bound(a + 1, a + 1 + numa, p[i].first) - a;
            p[i].second = std::lower_bound(b + 1, b + 1 + numb, p[i].second) - b;
        }

        for (int i = 1; i <= numa + numb; i++)
        {
            g[i].clear();
        }
        for (int i = 1; i <= n; i++)
        {
            g[p[i].first].push_back({p[i].second + numa, i});
            g[p[i].second + numa].push_back({p[i].first, i});
        }

        for (int i = 1; i <= numa + numb; i++)
        {
            tin[i] = 0;
        }
        timer = 0;
        for (int i = 1; i <= n; i++)
        {
            used[i] = false;
        }

        ans.clear();
        for (int i = 1; i <= numa + numb; i++)
        {
            if (tin[i] == 0)
            {
                dfs(i, -1);
            }
        }

        int tmp = -1;
        for (int i = 1; i <= n; i++)
        {
            if (!used[i])
            {
                if (tmp != -1)
                {
                    ans.push_back({tmp, i});
                    tmp = -1;
                }
                else
                {
                    tmp = i;
                }
            }
        }

        std::cout << ans.size() << "\n";
        for (auto pr : ans)
        {
            std::cout << pr.first << " " << pr.second << "\n";
        }
    }
}

詳細信息

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 7540kb

input:

3
2
0 0
0 1
1 0
1 1
2
0 0
0 1
0 2
0 3
2
0 0
1 1
2 2
3 3

output:

2
4 3
1 2
2
1 2
3 4
2
1 2
3 4

result:

wrong answer wrong number of friendly pairs: printed 2, but it is actually 0 (test case 3)