Submission #1237021

#TimeUsernameProblemLanguageResultExecution timeMemory
1237021MarwenElarbiParking (CEOI22_parking)C++20
0 / 100
88 ms36152 KiB
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back const int nax = 5e5+5; int place[nax][2]; int park[nax][2]; int outdeg[nax]; vector<int> dag[nax]; vector<int> adj[nax]; set<int> fre; bool vis[nax]; int cycle[nax]; vector<int> cur,concur; bool test=false; vector<pair<int,int>> ans; vector<int> topo; void deplace(int x,int y){ ans.push_back({x,y}); int topx = 1 - (park[x][0] == 0) - (park[x][1] == 0); int topy = 1 - (park[y][0] == 0) - (park[y][1] == 0); int vx = park[x][topx]; park[y][topy+1] = vx; int indx=0; if(place[vx][1] == x) indx=1; place[vx][indx]=y; park[x][topx] = 0; if(topx == 0) fre.insert(x); if(topy==-1){ if (indx == 1) swap(place[vx][0] , place[vx][1]); fre.erase(y); } } void dfs(int x){ if(cycle[x]==1){ test=true; return; } if(test) return; cycle[x]=1; for(auto u : dag[x]){ dfs(u); } cycle[x]=2; cur.push_back(x); } void dfs1(int x){ vis[x]=true; concur.push_back(x); for(auto u : adj[x]){ if(!vis[u]) dfs1(u); } } void run_case(){ int n,m; cin>>n>>m; for (int i = 1; i <= n; ++i) place[i][0]=place[i][1]=-1; for (int i = 1; i <= m; ++i) { cin>>park[i][0]>>park[i][1]; if(park[i][0]+park[i][1]==0) fre.insert(i); if(park[i][0]==park[i][1]) continue; if(place[park[i][0]][0] == -1) place[park[i][0]][0] = i; else place[park[i][0]][1] = i; if(park[i][1] != 0){ if(place[park[i][1]][1] == -1) place[park[i][1]][1] = i; else place[park[i][1]][0] = i; //cout <<park[i][1]<<" "<< place[park[i][1]][0] <<" "<< place[park[i][1]][0]<< endl; } dag[park[i][1]].push_back(park[i][0]); outdeg[park[i][1]]++; adj[park[i][1]].push_back(park[i][0]); adj[park[i][0]].push_back(park[i][1]); } //cout << place[1][0] << " "<<place[1][1]<<endl; for (int i = 1; i <= n; ++i) { if(place[i][0]==place[i][1]) continue; if(!vis[i]){ test=false; cur.clear(); concur.clear(); dfs1(i); for(auto u : concur) dfs(i); if(test){ if(fre.empty()){ cout << -1 << endl; return; }else{ int cnt = *fre.begin(); int lst=cnt; for(auto u : cur){ int temp = place[u][1]; deplace(place[u][1] , lst); lst = temp; } deplace(lst , cnt); } }else{ for(auto u : cur) topo.push_back(u); } } } reverse(topo.begin(),topo.end()); for(auto u : topo){ if(place[u][0]==place[u][1]) continue; if(outdeg[u] == 2){ if(fre.empty()){ cout << -1 <<endl; return; } int pivot = *fre.begin(); int y = place[u][1]; deplace(place[u][0] , pivot); deplace(y , pivot); }else if(outdeg[u] == 1){ deplace(place[u][1] , place[u][0]); }else if(outdeg[u] == 0){ deplace(place[u][1] , place[u][0]); } } cout << ans.size() << endl; for (auto u : ans) { cout << u.fi << " " << u.se << endl; } } int main() { run_case(); }
#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...