QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#473156 | #6414. Classical Maximization Problem | UESTC_Snow_Halation | WA | 0ms | 13252kb | C++17 | 2.2kb | 2024-07-11 22:36:20 | 2024-07-11 22:36:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr int max_n = 4e5+7;
double eps = 1e-8;
vector<int> edge[max_n];
map<int, int> x2n, y2n;
map<pair<int,int>,int> idx;
vector<pair<int, bool>> n2xy;
bool vis[max_n];
vector<pair<int, int>> ans;
struct Pair{
int a;
bool add(int x, int y) {
int b;
if (n2xy[x - 1].second) {
b = idx[{n2xy[y - 1].first, n2xy[x - 1].first}];
} else {
b = idx[{n2xy[x - 1].first, n2xy[y - 1].first}];
}
if (a > 0) {
ans.emplace_back(a, b);
a = -1;
return true;
} else {
a = b;
return false;
}
}
};
void clear() {
int n = n2xy.size();
ans.clear();
x2n.clear();
y2n.clear();
n2xy.clear();
for (int i = 0; i <= n; ++i) {
edge[i].clear();
}
memset(vis, 0, n + 5);
}
bool dfs(int u, int fa) {
vis[u] = true;
Pair p{-1};
for (int v: edge[u]) {
if (vis[v]) {
if (v != fa && v > u) {
p.add(u, v);
}
continue;
}
if (dfs(v, u)) {
p.add(u, v);
}
}
return fa && !p.add(u, fa);
}
void solve() {
int n;
cin >> n;
n <<= 1;
int x, y;
for (int i = 1; i <= n; ++i) {
cin >> x >> y;
idx[{x,y}] = i;
if (!x2n.count(x)) {
n2xy.emplace_back(x, false);
x2n[x] = n2xy.size();
}
if (!y2n.count(y)) {
n2xy.emplace_back(y, true);
y2n[y] = n2xy.size();
}
edge[x2n[x]].push_back(y2n[y]);
edge[y2n[y]].push_back(x2n[x]);
}
n = n2xy.size();
for (int i = 1; i <= n; ++i) {
if (!vis[i]) dfs(i, 0);
}
// for (int i = 1; i <= n; ++i) {
// cout << i << ": ";
// for (int it: edge[i]) {
// cout << it << ", ";
// }
// cout << '\n';
// }
int m = ans.size();
cout << m << '\n';
for (auto [x, y]: ans) {
cout << x << ' ' << y << '\n';
}
clear();
}
int main() {
// freopen("code.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
cin >> T;
// scanf("%d", &T);
for (int i = 1; i <= T; ++i) {
// cout << "Case " << i << ": ";
solve();
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 13252kb
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 0
result:
wrong output format Unexpected end of file - int32 expected (test case 3)