Submission #817019

#TimeUsernameProblemLanguageResultExecution timeMemory
817019ono_de206Parking (CEOI22_parking)C++14
20 / 100
95 ms16860 KiB
#include<bits/stdc++.h> using namespace std; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define in insert #define all(x) x.begin(),x.end() #define pb push_back #define eb emplace_back #define ff first #define ss second // #define int long long typedef long long ll; typedef vector<int> vi; typedef set<int> si; typedef multiset<int> msi; typedef pair<int, int> pii; typedef vector<pii> vpii; template<typename T, typename U> ostream & operator << (ostream &out, const pair<T, U> &c) { out << c.first << ' ' << c.second; return out; } template<typename T> ostream & operator << (ostream &out, vector<T> &v) { const int sz = v.size(); for (int i = 0; i < sz; i++) { if (i) out << ' '; out << v[i]; } return out; } template<typename T> istream & operator >> (istream &in, vector<T> &v) { for (T &x : v) in >> x; return in; } template<typename T> void mxx(T &a, T b){if(b > a) a = b;} template<typename T> void mnn(T &a, T b){if(b < a) a = b;} const int mxn = 2e5 + 10; int v[mxn][2], done[mxn]; vector<pair<int, int>> g[mxn]; void go() { int n, m; cin >> n >> m; set<int> em; for(int i = 1; i <= m; i++) { for(int j = 0; j < 2; j++) { cin >> v[i][j]; if(v[i][j]) g[v[i][j]].eb(j, i); } if(v[i][0] == 0) em.in(i); else if(v[i][0] == v[i][1]) done[v[i][0]] = 1; } vector<pair<int, int>> ans; for(int i = 1; i <= n; i++) { if(done[i]) continue; sort(all(g[i])); if(g[i][0].ff == 1) { if(em.empty()) { cout << -1 << '\n'; return; } int x = *em.begin(); ans.eb(g[i][0].ss, x); ans.eb(g[i][1].ss, x); v[g[i][0].ss][1] = v[g[i][1].ss][1] = 0; em.erase(x); v[x][0] = v[x][1] = i; done[i] = 1; } } function<void(int)> dfs = [&](int x) -> void { if(done[x]) return; if(g[x][1].ff == 0 && v[g[x][0].ss][1] == 0 && v[g[x][1].ss][1] == 0) { em.in(g[x][0].ss); ans.eb(g[x][0].ss, g[x][1].ss); v[g[x][0].ss][0] = 0; done[x] = 1; } else if(g[x][1].ff == 1 && v[g[x][0].ss][1] == 0) { ans.eb(g[x][1].ss, g[x][0].ss); v[g[x][1].ss][1] = 0; done[x] = 1; dfs(v[g[x][1].ss][0]); } }; for(int i = 1; i <= n; i++) { if(done[i]) continue; dfs(i); } for(int i = 1; i <= n; i++) { if(done[i]) continue; assert(g[i][1].ff == 1); int x = g[i][0].ss, y = g[i][1].ss; if(em.empty()) { cout << -1 << '\n'; return; } int p = *em.begin(); ans.eb(y, p); v[y][1] = 0; v[p][0] = i; g[i][1] = {0, p}; dfs(v[y][0]); } for(int i = 1; i <= n; i++) { if(!done[i]) { cout << -1 << '\n'; return; } } cout << ans.size() << '\n'; for(auto it : ans) { cout << it << '\n'; } } signed main() { // #ifndef ONO // freopen("file.in", "r", stdin); // freopen("file.out", "w", stdout); // #endif fast; int t = 1; // cin >> t; while(t--) { go(); } return 0; }

Compilation message (stderr)

Main.cpp: In function 'void go()':
Main.cpp:108:7: warning: unused variable 'x' [-Wunused-variable]
  108 |   int x = g[i][0].ss, y = g[i][1].ss;
      |       ^
#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...