제출 #997656

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997656		RaresFelix	Parking (CEOI22_parking)	C++17	100 / 100	489 ms	66564 KiB

Main

#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;
using ii = pair<int, int>;

int main() {
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<set<int> > L(n), G(n);

    vi A(2 * m, -1), P(2 * n, -1);
    set<int> LinLib;

    for(int i = 0; i < 2 * m; ++i) {
        int v;
        cin >> v;
        if(!v) continue;
        --v;
        v *= 2;
        if(P[v] != -1) ++v;
        P[v] = i;
        A[i] = v;
    }
    //set<int> Scoase;
    vi InDeg(n, 0), OutDeg(n, 0);
    for(int i = 0; i < m; ++i) {
        if(A[2 * i] == -1) LinLib.insert(i);
        if(A[2 * i + 1] != -1) {
            if(A[2 * i] == A[2 * i + 1]) continue;
            L[A[2 * i] / 2].insert(A[2 * i + 1] / 2);
            G[A[2 * i + 1] / 2].insert(A[2 * i] / 2);
            ++OutDeg[A[2 * i] / 2];
            ++InDeg[A[2 * i + 1] / 2];
        }
    }
    set<int> S[3][3]; /// culori dupa indeg/ outdeg
    for(int i = 0; i < n; ++i)
        S[InDeg[i]][OutDeg[i]].insert(i);

    vector<vi> LMono, LBi;
    vector<vi> Cicluri;

    vi viz(n, 0);
    function<int(int, int)> dfs0 = [&](int u, int p) {
        if(viz[u] == 1)
            return u;
        viz[u] = 1;
        for(auto it : L[u])
            if(it != p) return dfs0(it, u);
        for(auto it : G[u])
            if(it != p) return dfs0(it, u);
        return u;
    };

    function<void(int, int, bool&, int&, vi&)> dfscomp = [&](int u, int p, bool &cyc, int& dir, vi &comp) {
        if(viz[u] == 2) {
            cyc = 1;
            return;
        }
        viz[u] = 2;
        dir = max(dir, InDeg[u]);
        comp.push_back(u);
        int nr = 0;
        for(auto it : L[u])
            if(it != p) {
                dfscomp(it, u, cyc, dir, comp);
            } else ++nr;
        for(auto it : G[u])
            if(it != p) {
                dfscomp(it, u, cyc, dir, comp);
            } else ++nr;
        if(nr == 2) cyc = 1;
    };
    for(int i = 0; i < n; ++i) {
        if(!viz[i]) {
            int u = dfs0(i, -1), dir = 0;
            bool cyc = 0;
            vi comp;
            dfscomp(u, -1, cyc, dir, comp);
            if(cyc) Cicluri.push_back(comp);
            else {
                if(dir == 2) LBi.push_back(comp);
                else LMono.push_back(comp);
            }
        }
    }
    
    int ok = 1;

    vector<ii> Sol;

    auto move = [&](int from, int to) {
        Sol.push_back({from, to});
        int pf = 2 * from, pdest = 2 * to;
        if(A[pf + 1] != -1) {
            L[A[pf] / 2].erase(A[pf + 1] / 2);
            G[A[pf + 1] / 2].erase(A[pf] / 2);
            --OutDeg[A[pf] / 2];
            --InDeg[A[pf + 1] / 2];
            ++pf;
        } else LinLib.insert(from);
        if(A[pdest] != -1) {
            L[A[pdest] / 2].insert(A[pf] / 2);
            G[A[pf] / 2].insert(A[pdest] / 2);
            ++InDeg[A[pf] / 2];
            ++OutDeg[A[pdest] / 2];
            ++pdest;
        } else LinLib.erase(to);
        A[pdest] = A[pf];
        A[pf] = -1;
        P[A[pdest]] = pdest;
    };

    auto scotdeg2 = [&](int u) {
        int liber;
        if(LinLib.empty()) {
            cout << "-1\n";
            exit(0);
        }
        liber = *LinLib.begin();
        move(P[2 * u] / 2, liber);
        move(P[2 * u + 1] / 2, liber);
    };

    auto solveSir = [&](vi S) {
        if(S.empty()) return;
        auto singur = [&](int u) {
            if(P[2 * u] / 2 != P[2 * u + 1] / 2)
                move(P[2 * u] / 2, P[2 * u + 1] / 2);
        };
        if(S.size() == 1) {
            int u = S[0];
            singur(u);
            return;
        }
        deque<int> D;
        for(auto it : S) D.push_back(it);

        auto scoate = [&](int u) {
            int a = P[2 * u], b = P[2 * u + 1];
            if(b & 1) swap(a, b);
            move(a / 2, b / 2);
        };
        while(!D.empty()) {
            if(InDeg[D.back()] == 0 && OutDeg[D.back()] == 0) {
                singur(D.back());
                D.pop_back();
                continue;
            }
            if(InDeg[D.front()] == 1) {
                scoate(D.front());
                D.pop_front();
                continue;
            } 
            if(InDeg[D.back()] == 1) {
                scoate(D.back());
                D.pop_back();
                continue;
            } 
            int u = D.back(), p = -1;
            vi Acum;
            while(InDeg[u] != 2) {
                Acum.push_back(D.back());
                D.pop_back();
                u = D.back();
            }
            //il scot pe u acum
            scotdeg2(u);
            D.pop_back();
            
            reverse(Acum.begin(), Acum.end());
            for(int i = 0; i + 1 < Acum.size(); ++i)
                scoate(Acum[i]);
            if(!Acum.empty())
                singur(Acum.back());
            else { 
                singur(D.back()); 
                D.pop_back();
            }
        }
    };

    auto solveCyc = [&](vi C) {
        if(C.size() == 1) {
            return; /// e deja bun daca e identificat ca ciclu
        }
        deque<int> D;
        for(auto it : C)
            D.push_back(it);
        for(int i = 0; i < n; ++i) {
            if(InDeg[D.back()] == 2) {
                scotdeg2(D.back());
                D.pop_back();
                vi S;
                for(auto it : D) S.push_back(it);
                solveSir(S);
                return;
            }
            D.push_front(D.back());
            D.pop_back();
        }
        ///e full ciclic
        int u = D.back(), a = P[2 * u], b = P[2 * u + 1];
        if(b & 1) swap(a, b);
        int liber;
        if(LinLib.empty()) {
            cout << "-1\n";
            exit(0);
        }
        liber = *LinLib.begin();
        int urm = A[a - 1];
        move(a / 2, liber);
        if(D.front() == urm) {
            D.push_back(D.front());
            D.pop_front();
        }
        else {
            D.push_front(D.back());
            D.pop_back();
        }
        vi S;
        for(auto it : D) S.push_back(it);
        solveSir(S);
        return;
    };
    
    for(auto it : LMono) solveSir(it);
    for(auto it : LBi) solveSir(it);
    for(auto it : Cicluri) solveCyc(it);

    if(!ok) {
        cout << "-1\n";
        return 0;
    }
    cout << Sol.size() << "\n";
    for(auto [a, b] : Sol)
        cout << a + 1 << " " << b + 1 << "\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In lambda function:
Main.cpp:175:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |             for(int i = 0; i + 1 < Acum.size(); ++i)
      |                            ~~~~~~^~~~~~~~~~~~~
Main.cpp:163:31: warning: unused variable 'p' [-Wunused-variable]
  163 |             int u = D.back(), p = -1;
      |                               ^

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