QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#178701#6414. Classical Maximization ProblemalexzhanUSWA 0ms3832kbC++173.2kb2023-09-14 11:21:292023-09-14 11:21:30

Judging History

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

  • [2023-09-14 11:21:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3832kb
  • [2023-09-14 11:21:29]
  • 提交

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)