QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#178701 | #6414. Classical Maximization Problem | alexzhanUS | WA | 0ms | 3832kb | C++17 | 3.2kb | 2023-09-14 11:21:29 | 2023-09-14 11:21:30 |
Judging History
answer
#include <iostream>
#include <map>
#include <vector>
#include <set>
using namespace std;
class Endpoint {
public:
long long endpoint;
int edgeIndex;
bool marked = false;
Endpoint(long long endpoint, int edgeIndex): endpoint(endpoint), edgeIndex(edgeIndex) {}
};
void buildDFSTree(map<long long, vector<Endpoint>>& graph, set<long long>& visited, long long node) {
// *NOTE: the edge from a node to its parent is marked (false) as a back edge.
visited.insert(node);
for (Endpoint& edge : graph[node]) {
if (visited.find(edge.endpoint) == visited.end()) { // not visited before
edge.marked = true;
buildDFSTree(graph, visited, edge.endpoint);
}
// if it is already visited, it is a back edge, so you don't really need to do anything
}
}
bool pairEdges(map<long long, vector<Endpoint>>& graph, vector<pair<int, int>>& pairs, long long node, long long parent) {
// return true if you used the edge from the node to its parent.
// return false otherwise.
set<int> notUsedEdges;
int parentEdge = 0;
for (Endpoint& edge : graph[node]) {
if (edge.marked) { // it is a spanning edge
if (!pairEdges(graph, pairs, edge.endpoint, node)) { // if edge is not used
notUsedEdges.insert(edge.edgeIndex);
}
} else { // it is a back edge.
if (edge.endpoint != parent) {
notUsedEdges.insert(edge.edgeIndex);
} else {
parentEdge = edge.edgeIndex;
}
}
}
while (notUsedEdges.size() >= 2) {
int a = *notUsedEdges.begin();
notUsedEdges.erase(notUsedEdges.begin());
int b = *notUsedEdges.begin();
notUsedEdges.erase(notUsedEdges.begin());
pairs.emplace_back(a, b);
}
if (notUsedEdges.size() == 1) {
if (parentEdge != 0) {
pairs.emplace_back(parentEdge, *notUsedEdges.begin());
}
return true;
} else {
return false;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int numOfTestCases;
cin >> numOfTestCases;
map<long long, vector<Endpoint>> graph;
for (int i = 0; i < numOfTestCases; i++) {
int numOfPoints;
cin >> numOfPoints;
for (int j = 0; j < (2 * numOfPoints); j++) {
long long x, y;
cin >> x >> y;
y += 2e9 + 1;
graph[x].emplace_back(y, j + 1);
graph[y].emplace_back(x, j + 1);
}
set<long long> visited;
buildDFSTree(graph, visited, graph.begin()->first);
vector<pair<int, int>> pairs;
pairEdges(graph, pairs, graph.begin()->first, -1e9 - 1);
cout << pairs.size() << "\n";
set<int> points;
for (int j = 1; j <= 2 * numOfPoints; j++) {
points.insert(j);
}
for (auto& pair : pairs) {
cout << pair.first << " " << pair.second << "\n";
points.erase(pair.first);
points.erase(pair.second);
}
while (points.size() > 0) {
cout << *points.begin() << " ";
points.erase(points.begin());
cout << *points.begin() << "\n";
points.erase(points.begin());
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3832kb
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 2 1 3 4 4 2 1 3 1 2 3 4 5 2 2 3 2 3 3 4 4 1 2
result:
wrong answer Integer parameter [name=k] equals to 4, violates the range [0, 2] (test case 2)