QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181975#6414. Classical Maximization ProblemalexzhanUSTL 0ms0kbC++174.1kb2023-09-17 06:58:582023-09-17 06:58:58

Judging History

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

  • [2023-09-17 06:58:58]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2023-09-17 06:58:58]
  • 提交

answer

#include <iostream>
#include <map>
#include <vector>
#include <set>

using namespace std;

class Neighbor {
public:
    long long vertex;
    int edgeIndex;
    bool isTreeEdge = false;
    Neighbor(long long axisValue, int edgeIndex): vertex(axisValue), edgeIndex(edgeIndex) {}
};

void buildDfsTree(map<long long, vector<Neighbor>>& adjacencyMatrix, set<long long>& visited, long long node, int& time, map<long long, int>& nodeToEntryTime) {
    // *NOTE: the edge from a node to its parent is marked as a back edge.
    time++;
    nodeToEntryTime[node] = time;
    visited.insert(node);
    for (Neighbor& neighbor : adjacencyMatrix[node]) {
        if (visited.find(neighbor.vertex) == visited.end()) { // not visited before
            neighbor.isTreeEdge = true;
            buildDfsTree(adjacencyMatrix, visited, neighbor.vertex, time, nodeToEntryTime);
        }
        // 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, map<long long, int>& nodeToEntryTime) {
    // return true if you used the edge from the node to its parent.
    // return false otherwise.
    set<int> notUsedEdges;
    int parentEdgeIndex = 0;
    for (Neighbor& neighbor : adjacencyMatrix[node]) {
        if (neighbor.isTreeEdge) { // it is a spanning edge
            if (!pairEdges(adjacencyMatrix, pairs, neighbor.vertex, node, nodeToEntryTime)) { // if neighbor is not used
                notUsedEdges.insert(neighbor.edgeIndex);
            }
        } else { // it is a back edge.
            if (nodeToEntryTime[neighbor.vertex] > nodeToEntryTime[node]) {
                //TODO: add a check to make sure that this back edge is connecting node to something in its subtree
                // rather than going upwards
                notUsedEdges.insert(neighbor.edgeIndex);
            } else if (neighbor.vertex == parent) {
                parentEdgeIndex = neighbor.edgeIndex;
            }
        }
    }
    auto iterator = notUsedEdges.begin();
    auto iterator2 = ++notUsedEdges.begin();
    while (iterator != notUsedEdges.end() && iterator2 != notUsedEdges.end()) {
        pairs.emplace_back(*iterator, *iterator2);
        ++++iterator;
        ++++iterator2;
    }
    if (notUsedEdges.size() == 1 && parentEdgeIndex != 0) {
        pairs.emplace_back(parentEdgeIndex, *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> allNodes;
        for (int j = 0; j < (2 * n); j++) {
            long long x, y;
            cin >> x >> y;
            y += 2e9 + 1;
            adjacencyMatrix[x].emplace_back(y, j + 1);
            adjacencyMatrix[y].emplace_back(x, j + 1);
            allNodes.insert(x);
            allNodes.insert(y);
        }
        set<long long> visited;
        vector<pair<int, int>> pairs;
        map<long long, int> nodeToEntryTime;
        int time = 0;
        for (auto& node : allNodes) {
            if (visited.find(node) == visited.end()) {
                buildDfsTree(adjacencyMatrix, visited, node, time, nodeToEntryTime);
                pairEdges(adjacencyMatrix, pairs, node, -1e9 - 1, nodeToEntryTime);
            }
        }
        cout << pairs.size() << "\n";
        vector<bool> usedPoints(2 * n + 1);
        for (auto& pair : pairs) {
            cout << pair.first << " " << pair.second << "\n";
            usedPoints[pair.first] = true;
            usedPoints[pair.second] = true;
        }
        vector<int> notUsedPoints;
        for (int j = 1; j <= 2 * n; j++) {
            if (!usedPoints[j]) {
                notUsedPoints.push_back(j);
            }
        }
        for (int index = 0; index < notUsedPoints.size(); index += 2) {
            cout << notUsedPoints[index] << " " << notUsedPoints[index + 1] << "\n";
        }
    }
    return 0;
}

详细

Test #1:

score: 0
Time Limit Exceeded

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:


result: