제출 #997656

#제출 시각아이디문제언어결과실행 시간메모리
997656RaresFelixParking (CEOI22_parking)C++17
100 / 100
489 ms66564 KiB
#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;
      |                               ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...