QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#179703 | #6414. Classical Maximization Problem | Curious_Droid | WA | 0ms | 7540kb | C++23 | 3.1kb | 2023-09-15 02:03:12 | 2023-09-15 02:03:12 |
Judging History
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)