제출 #632109

#제출 시각아이디문제언어결과실행 시간메모리
632109arayiParking (CEOI22_parking)C++17
100 / 100
435 ms87412 KiB
// Arayi #include <bits/stdc++.h> #define fr first #define sc second #define MP make_pair #define ad push_back #define PB push_back #define fastio \ ios_base::sync_with_stdio(false); \ cin.tie(0); \ cout.tie(0); #define lli long long int #define y1 arayikhalatyan #define j1 jigglypuff #define ld long double #define itn int #define pir pair<int, int> #define all(x) (x).begin(), (x).end() #define str string #define enl endl #define en endl #define cd complex<long double> #define vcd vector<cd> #define vii vector<int> #define vlli vector<lli> using namespace std; lli gcd(lli a, lli b) { return (b == 0LL ? a : gcd(b, a % b)); } ld dist(ld x, ld y1, ld x2, ld y2) { return sqrt((x - x2) * (x - x2) + (y1 - y2) * (y1 - y2)); } lli S(lli a) { return (a * (a + 1LL)) / 2; } mt19937 rnd(363542); char vow[] = {'a', 'e', 'i', 'o', 'u'}; int dx[] = {0, -1, 0, 1, -1, -1, 1, 1, 0}; int dy[] = {-1, 0, 1, 0, -1, 1, -1, 1, 0}; char dc[] = {'R', 'D', 'L', 'U'}; const int N = 5e5 + 20; const lli mod = 1e9 + 7; const ld pi = acos(-1); const ld e = 1e-13; const int T = 128; lli bp(lli a, lli b = mod - 2LL) { lli ret = 1; while (b) { if (b & 1) ret *= a, ret %= mod; a *= a; a %= mod; b >>= 1; } return ret; } ostream &operator<<(ostream &c, pir a) { c << a.fr << " " << a.sc; return c; } template <class T> void maxi(T &a, T b) { a = max(a, b); } template <class T> void mini(T &a, T b) { a = min(a, b); } int n, m; vii az, ind[N], g[N], g1[N]; bool col[N]; int a[N][2], t[N]; vii tp[3]; vector<pir> pat; vii gg[N], gg1[N]; priority_queue<pair<int, int>> q; void dfs(int v, int x1) { if (t[v] == 1) gg1[x1].ad(v), gg[v].ad(x1); for (auto p : g1[v]) dfs(p, x1); } vii sm; void dfs1(int v) { bool bl = 0; for (auto p : g[v]) { if(!col[p]) { dfs1(p); bl = 1; } } if(!bl) sm.ad(v); } void han(int i1) { if (col[i1]) return; if (t[i1] == 3) { if (az.empty()) { cout << -1 << endl; exit(0); } pat.ad(MP(ind[i1][0], az.back())); pat.ad(MP(ind[i1][1], az.back())); az.pop_back(); col[i1] = 1; for (auto p : gg1[i1]) { for (int i = 0; i < gg[p].size(); i++) { if (gg[p][i] == i1) { swap(gg[p][i], gg[p].back()); gg[p].pop_back(); break; } } q.push(MP(-gg[p].size(), p)); } for (auto p : g1[i1]) han(p); } else if (t[i1] == 2) { col[i1] = 1; pat.ad(MP(ind[i1][1], ind[i1][0])); for (auto p : g1[i1]) han(p); } else { if (gg[i1].empty()) { sm.clear(); dfs1(i1); if (sm[0] == i1) { pat.ad(MP(ind[i1][1], ind[i1][0])); az.ad(ind[i1][1]); col[i1] = 1; } else for(auto p : sm) han(p); } } } int main() { fastio; cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b; cin >> a >> b; ::a[i][0] = a, ::a[i][1] = b; if (a == 0) az.ad(i); else ind[a].ad(i), ind[b].ad(i); if (a == b) col[a] = 1; } for (int i = 1; i <= n; i++) { if (col[i]) continue; int i1 = ind[i][0], i2 = ind[i][1]; if (a[i1][0] == i && a[i2][0] == i) { if (a[i1][1]) g[i].ad(a[i1][1]); if (a[i2][1]) g[i].ad(a[i2][1]); tp[0].ad(i); t[i] = 1; } if (a[i1][1] == i && a[i2][0] == i) swap(ind[i][0], ind[i][1]), swap(i1, i2); if (a[i1][0] == i && a[i2][1] == i) { if (a[i1][1]) g[i].ad(a[i1][1]); g1[i].ad(a[i2][0]); tp[1].ad(i); t[i] = 2; } if (a[i1][1] == i && a[i2][1] == i) { g1[i].ad(a[i1][0]); g1[i].ad(a[i2][0]); tp[2].ad(i); t[i] = 3; } /*cout << i << "-"; for(auto p : g[i]) cout << p << " "; cout << endl;*/ } for (auto p : tp[2]) dfs(p, p); /*for(auto p : tp[0]) { cout << p << "-"; for(auto p1 : gg[p]) cout << p1 << " "; cout << endl; } for(auto p : tp[2]) { cout << p << "-"; for(auto p1 : gg1[p]) cout << p1 << " "; cout << endl; }*/ for (auto p : tp[0]) q.push(MP(-gg[p].size(), p)); while (!q.empty()) { auto p = q.top(); q.pop(); if (col[p.sc]) continue; sm.clear(); dfs1(p.sc); for (auto p1 : sm) han(p1); } for (int i = 1; i <= n; i++) { if (!col[i] && t[i] == 3) han(i); } for (int i = 1; i <= n; i++) { if (!col[i] && t[i] == 2) { if (az.empty()) { cout << -1 << endl; exit(0); } pat.ad(MP(ind[i][1], az.back())); ind[i][1] = az.back(); han(g1[i][0]); } } cout << pat.size() << endl; for (auto p : pat) cout << p.fr << " " << p.sc << "\n"; return 0; } /* __ *(><)* \/ / ||/ --|| || /\ / \ / \ */

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

Main.cpp: In function 'void han(int)':
Main.cpp:124:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for (int i = 0; i < gg[p].size(); i++)
      |                             ~~^~~~~~~~~~~~~~
#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...