Submission #1309966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309966		dorkikann	Parking (CEOI22_parking)	C++20	100 / 100	64 ms	141032 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

pair<int, int> Parking[N];
pair<int, int> Positions[N];

//0 - bottom, 1 - top
pair<int, bool> Graph[N][2];
bitset<N> visited;

vector<int> Free;
vector<pair<int, int>> Solution;

void AddMove(int a, int b)
{
    Solution.push_back({a, b});

    if(Parking[b].first == 0) {
        if(Parking[a].second != 0)
            swap(Parking[a].second, Parking[b].first);
        else
            swap(Parking[a].first, Parking[b].first);
    } else {
        if(Parking[a].second != 0)
            swap(Parking[a].second, Parking[b].second);
        else
            swap(Parking[a].first, Parking[b].second);
    }
}

void BuildGraph(int n, int m)
{
    bool work = true;
    for(int i = 1; i <= m; i++) {
        Graph[i][0] = {-1, -1};
        Graph[i][1] = {-1, -1};
    }

    for(int i = 1; i <= n; i++) {
        if(Positions[i].first == Positions[i].second)
            continue;

        bool a1 = (Parking[Positions[i].first].second == i);
        bool a2 = (Parking[Positions[i].second].second == i);

        Graph[Positions[i].first][a1] = {Positions[i].second, a2};
        Graph[Positions[i].second][a2] = {Positions[i].first, a1};
    }
}

pair<int, int> needed = {-1, -1};
vector<pair<int, int>> Add;

int Fun(int u)
{
    int vertex = u;

    while(Graph[vertex][1].second != 1 && Graph[vertex][1].first != -1) {
        Add.push_back({vertex, Graph[vertex][1].first});
        vertex = Graph[vertex][1].first;
        visited[vertex];
    }

    if(Graph[vertex][1].first == -1) {
        while(!Add.empty()) {
            AddMove(Add.back().first, Add.back().second);
            Add.pop_back();
        }
        return -1;
    }

    if(Free.size() == 0)
        return 0;
    
    AddMove(vertex, Free.back());
    AddMove(Graph[vertex][1].first, Free.back());
    Free.pop_back();

    while(!Add.empty()) {
        AddMove(Add.back().first, Add.back().second);
        Add.pop_back();
    }
    return Graph[vertex][1].first;
}

bool DFS1(int u, bool which) 
{
    visited[u] = 1;
    
    if(which == 0) {
        if(Graph[u][0].second == 1) {
            AddMove(Graph[u][0].first, u);

            if(!DFS1(Graph[u][0].first, 0))
                return false;
        } else {
            needed = {u, Graph[u][0].first};

            if(!DFS1(Graph[u][0].first, 1))
                return false;
        }
    } else {
        if(Graph[u][1].second == 0) {
            int x = Fun(u);
            if(x == 0)
                return false;

            if(needed.first != -1) {
                AddMove(needed.first, needed.second);
                Free.push_back(needed.first);
                needed = {-1, -1};
            }

            if(x != -1) {
                if(!DFS1(x, 0))
                    return false;
            }
        } else if(Graph[u][1].first != -1) {
            if(Free.size() == 0)
                return false;

            AddMove(u, Free.back());
            AddMove(Graph[u][1].first, Free.back());
            Free.pop_back();

            if(needed.first != -1) {
                AddMove(needed.first, needed.second);
                Free.push_back(needed.first);
                needed = {-1, -1};
            }

            if(!DFS1(Graph[u][1].first, 0))
                return false;
        } else {
            if(needed.first != -1) {
                AddMove(needed.first, needed.second);
                Free.push_back(needed.first);
                needed = {-1, -1};
            }
        }
    }
    return true;
}

void DFS2(int u, int pos) 
{
    visited[u] = 1;
    AddMove(u, pos);

    if(!visited[Graph[u][0].first])
        DFS2(Graph[u][0].first, u);
}

bool DFSHelp(int u, bool which)
{
    if(which == 0) {
        if(Graph[u][0].second == 1)
            return DFSHelp(Graph[u][0].first, 0);
        else
            return DFSHelp(Graph[u][0].first, 1);
    } else {
        if(Graph[u][1].second == 0)
            return DFSHelp(Graph[u][1].first, 1);
        else if(Graph[u][1].first != -1)
            return false;  
    }
    return true;
}

bool Solve(int n, int m)
{
    for(int i = 1; i <= m; i++) {
        if(!visited[i] && Parking[i].first != Parking[i].second) {
            if(Graph[i][1].first == -1 && DFSHelp(i, 0)) {
                if(!DFS1(i, 0))
                    return false;
            }
        }
    }
    for(int i = 1; i <= m; i++) {
        if(!visited[i] && Parking[i].first != Parking[i].second) {
            if(Graph[i][1].first == -1) {
                if(!DFS1(i, 0))
                    return false;
            }
        }
    }
    
    for(int i = 1; i <= m; i++) {
        if(!visited[i] && Parking[i].first != Parking[i].second) {
            if(Graph[i][1].second == 1) {
                if(Free.size() == 0)
                    return false;

                AddMove(i, Free.back());
                AddMove(Graph[i][1].first, Free.back());

                Free.pop_back();
                Graph[Graph[i][1].first][1].first = -1;
                Graph[i][1].first = -1;

                if(!DFS1(i, 0))
                    return false;
            }
        }
    }

    for(int i = 1; i <= m; i++) {
        if(!visited[i] && Parking[i].first != Parking[i].second) {
            if(Free.size() == 0)
                return false;

            int c = Parking[i].second;
            DFS2(i, Free.back());
            
            if(Positions[c].first == i)
                swap(Positions[c].first, Positions[c].second);
            AddMove(Free.back(), Positions[c].first);
        }
    }

    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m, a, b;
    cin >> n >> m;

    for(int i = 1; i <= m; i++) {
        cin >> a >> b;
        Parking[i] = {a, b};

        if(a == 0 && b == 0)
            Free.push_back(i);

        if(Positions[a].first == 0)
            Positions[a].first = i;
        else
            Positions[a].second = i;

        if(Positions[b].first == 0)
            Positions[b].first = i;
        else
            Positions[b].second = i;
    }

    BuildGraph(n, m);
    
    if(!Solve(n, m)) 
        cout << "-1\n";
    else {
        cout << Solution.size() << "\n";
        
        for(auto [x, y] : Solution)
            cout << x << " " << y << "\n";
    }
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15