QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#181947 | #6414. Classical Maximization Problem | alexzhanUS | WA | 1ms | 3840kb | C++17 | 4.2kb | 2023-09-17 06:05:39 | 2023-09-17 06:05:39 |
Judging History
answer
#include <iostream>
#include <map>
#include <vector>
#include <set>
#pragma GCC optimization("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimize("03")
#pragma GCC optimize("03, fast-math")
using namespace std;
class Neighbor {
public:
long long axisValue;
int edgeIndex;
bool marked = false;
Neighbor(long long axisValue, int edgeIndex): axisValue(axisValue), edgeIndex(edgeIndex) {}
};
void buildDFSTree(map<long long, vector<Neighbor>>& adjacencyMatrix, 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 (Neighbor& edge : adjacencyMatrix[node]) {
if (visited.find(edge.axisValue) == visited.end()) { // not visited before
edge.marked = true;
buildDFSTree(adjacencyMatrix, visited, edge.axisValue);
}
// 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<Neighbor>>& adjacencyMatrix, 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 (Neighbor& neighbor : adjacencyMatrix[node]) {
if (neighbor.marked) { // it is a spanning neighbor
if (!pairEdges(adjacencyMatrix, pairs, neighbor.axisValue, node)) { // if neighbor is not used
notUsedEdges.insert(neighbor.edgeIndex);
}
} else { // it is a back neighbor.
if (neighbor.axisValue != parent) {
notUsedEdges.insert(neighbor.edgeIndex);
} else {
parentEdge = neighbor.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;
for (int i = 0; i < numOfTestCases; i++) {
int n;
cin >> n;
map<long long, vector<Neighbor>> adjacencyMatrix;
set<long long> allVertices;
for (int j = 0; j < (2 * n); j++) {
long long x, y;
cin >> x >> y;
// TODO: why do we need this?
y += 2e9 + 1;
adjacencyMatrix[x].emplace_back(y, j + 1);
adjacencyMatrix[y].emplace_back(x, j + 1);
// Bug: what if x and y are the same? //// I literally did y += 2e9 + 1 in order to make sure that x and y are not the same
allVertices.insert(x);
allVertices.insert(y);
}
set<long long> visited;
vector<pair<int, int>> pairs;
for (auto& vertex : allVertices) {
if (visited.find(vertex) == visited.end()) {
buildDFSTree(adjacencyMatrix, visited, vertex);
pairEdges(adjacencyMatrix, pairs, vertex, -1e9 - 1);
}
}
cout << pairs.size() << "\n";
set<int> points;
for (int j = 1; j <= 2 * n; j++) {
points.insert(j);
}
for (auto& pair : pairs) {
cout << pair.first << " " << pair.second << "\n";
points.erase(pair.first);
points.erase(pair.second);
}
// There is a more efficient way of doing it.
// One option is to use vector<boolean> to track what points are used already, and then insert all unused
// points to a separate vector. Then scan through the vector once to print out pairs.
// Another option is to reuse set<int> to keep track of unused points, and then use iterator arithmetics (iterator++).
auto iterator = points.begin();
while (iterator != points.end()) {
cout << *iterator << " " << *++iterator << "\n";
}
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3840kb
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 2 1 2 3 4 0 1 2 2 3 3 4 4 4
result:
wrong answer point 2 used twice (test case 3)