QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181947#6414. Classical Maximization ProblemalexzhanUSWA 1ms3840kbC++174.2kb2023-09-17 06:05:392023-09-17 06:05:39

Judging History

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

  • [2023-09-17 06:05:39]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3840kb
  • [2023-09-17 06:05:39]
  • 提交

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)