| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1044295 |
2024-08-05T08:40:17 Z |
ㅇㅇ(#11061) |
Parking (CEOI22_parking) |
C++17 |
|
52 ms |
48276 KB |
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using pii=array<int,2>;
const int N=200005;
int n,m,b[N],t[N];
vector<int> g[N],up[N],l[N];
bool vis[N];
vector<int> V,e;
bool ok=true,isCyc;
int outcnt;
vector<pii> ans;
vector<vector<int>> cycles;
void fail(){
cout<<"-1\n";
exit(0);
}
void upd(int i){
vector<int> nl;
for(int c: l[i]) if(b[c]==i||t[c]==i) nl.push_back(c);
l[i]=nl;
up[i].clear();
for(int c: l[i]) if(b[c]==i&&t[c]) up[i].push_back(t[c]);
g[i].clear();
for(int c: l[i]) if(b[c]&&t[c]){
if(b[c]!=i) g[i].push_back(b[c]);
if(t[c]!=i) g[i].push_back(t[c]);
}
}
void Do(int x,int y){
debug(x,y);
assert(b[x]);
if(t[x]){
assert(!b[y]||t[x]==b[y]);
if(!b[y]) b[y]=t[x];
else t[y]=t[x];
l[y].push_back(t[x]);
t[x]=0;
} else{
assert(!b[y]||b[x]==b[y]);
if(!b[y]) b[y]=b[x];
else t[y]=b[x];
l[y].push_back(b[x]);
b[x]=0;
}
upd(x); upd(y);
ans.push_back({x,y});
}
bool chk(int i){
int x=l[i][0],y=l[i][1];
if(!t[x]&&!t[y]){
return true;
} else if(!!t[x]+!!t[y]==1){
if(t[x]) swap(x,y);
if(i==t[y]){
return true;
}
}
return false;
}
void dfs(int u){
V.push_back(u);
vis[u]=1;
isCyc&=g[u].size()==2;
if(up[u].size()==2) outcnt++;
for(int v: g[u]) if(!vis[v]) dfs(v);
}
int findDown(int i){
if(b[l[i][0]]==i) return l[i][0];
return l[i][1];
}
int findUp(int i){
if(t[l[i][0]]==i) return l[i][0];
return l[i][1];
}
void solvePath(){
debug(V,"path");
if(e.empty()) fail();
int s=0;
for(int u: V) if(g[u].size()==1) s=u;
for(int u: V) vis[u]=0;
V.clear();
dfs(s);
debug(V);
for(int s=0;s<(int)V.size();){
int e1=0,e2=0;
while(up[V[e1]].size()==1) e1++;
e2=e1+1;
while(e2+1<(int)V.size()&&up[V[e2]].size()==1) e2++;
int x=l[V[e1]][0],y=l[V[e1]][1];
debug(V[s],V[e1],V[e2]);
Do(x,e[0]);
Do(y,e[0]);
for(int i=e1-1;i>s;i--) Do(findUp(V[i]),findDown(V[i]));
int x1=l[V[s]][0],y1=l[V[s]][1];
Do(x1,y1);
e[0]=x1;
for(int i=e1+1;i<e2;i++) Do(findUp(V[i]),findDown(V[i]));
if(e2==(int)V.size()-1) break;
s=e2;
}
int i=V.back();
Do(l[i][0],l[i][1]);
e.push_back(l[i][0]);
}
void solveCycle(){
debug(V,"cycle");
if(!outcnt){
if(e.empty()) fail();
int s=V[0],x=t[findDown(s)];
V.clear();
while(x!=s){
V.push_back(x);
x=t[findDown(x)];
}
x=findUp(s);
Do(x,e[0]);
for(int u: V) Do(findUp(u),findDown(u));
Do(e[0],findDown(s));
}
if(outcnt==1){
if(e.empty()) fail();
int s=0,t=0;
for(int u: V){
if(up[u].size()==0) s=u;
if(up[u].size()==2) t=u;
}
Do(l[s][0],e[0]);
Do(l[s][1],e[0]);
for(int i=b[l[s][0]];i!=t;i=b[findUp(i)]) Do(findUp(i),findDown(i));
for(int i=b[l[s][1]];i!=t;i=b[findUp(i)]) Do(findUp(i),findDown(i));
Do(l[t][1],l[t][0]);
e[0]=l[t][1];
}
if(e.size()<=1) fail();
int s=0;
for(int u: V) if(up[u].size()==0) s=u;
int emp=e.back();
e.pop_back();
Do(l[s][0],emp);
Do(l[s][1],emp);
b[emp]=t[emp]=s;
t[l[s][0]]=t[l[s][1]]=0;
int i;
for(i=b[l[s][0]];up[i].size()!=1;i=b[findUp(i)]) Do(findUp(i),findDown(i));
for(i=b[l[s][1]];up[i].size()!=1;i=b[findUp(i)]) Do(findUp(i),findDown(i));
for(int u: V) vis[u]=0;
V.clear();
dfs(i);
solvePath();
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>b[i]>>t[i];
if(b[i]!=t[i]) ok=false;
if(b[i]){
l[b[i]].push_back(i);
}
if(t[i]){
l[t[i]].push_back(i);
if(b[i]!=t[i]){
up[b[i]].push_back(t[i]);
g[b[i]].push_back(t[i]);
g[t[i]].push_back(b[i]);
}
}
}
if(ok){
cout<<"0\n";
return 0;
}
if(n==m) fail();
for(int i=1;i<=m;i++) if(!b[i]) e.push_back(i);
queue<int> que;
for(int i=1;i<=n;i++){
int x=l[i][0],y=l[i][1];
if(x==y){
vis[i]=1;
continue;
}
if(chk(i)){
vis[i]=1;
que.push(i);
}
}
while(que.size()){
int i=que.front(); que.pop();
int x=l[i][0],y=l[i][1];
if(!t[x]&&!t[y]){
Do(y,x);
t[x]=i;
b[y]=0;
e.push_back(y);
} else{
if(t[x]) swap(x,y);
Do(y,x);
t[x]=i;
t[y]=0;
if(!vis[b[y]]&&chk(b[y])){
vis[b[y]]=1;
que.push(b[y]);
}
}
}
for(int s=1;s<=n;s++) if(!vis[s]){
V.clear();
isCyc=true;
outcnt=0;
dfs(s);
if(!isCyc) solvePath();
else cycles.push_back(V);
}
for(vector<int> cyc: cycles){
for(int u: cyc) vis[u]=0;
V.clear();
isCyc=true;
outcnt=0;
dfs(cyc[0]);
solveCycle();
}
cout<<ans.size()<<"\n";
for(auto [x,y]: ans) cout<<x<<" "<<y<<"\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 4 |
Runtime error |
10 ms |
29532 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
48276 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
29784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
13 ms |
29784 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
29788 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 2 |
Correct |
3 ms |
14680 KB |
Output is correct |
| 3 |
Correct |
2 ms |
14680 KB |
Output is correct |
| 4 |
Runtime error |
10 ms |
29532 KB |
Execution killed with signal 11 |
| 5 |
Halted |
0 ms |
0 KB |
- |
