oj.uz

답안 #1044300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1044300 2024-08-05T08:43:04 Z ㅇㅇ(#11061) Parking (CEOI22_parking) C++17
0 / 100
 83 ms 47252 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;
		}
		int x=l[s][0],y=l[s][1];
		Do(x,e[0]);
		Do(y,e[0]);
		for(int i=b[x];i!=t;i=b[findUp(i)]) Do(findUp(i),findDown(i));
		for(int i=b[y];i!=t;i=b[findUp(i)]) Do(findUp(i),findDown(i));
		x=l[t][0],y=l[t][1];
		Do(x,y);
		e[0]=x;
	}
	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();
	int x=l[s][0],y=l[s][1];
	Do(x,emp);
	Do(y,emp);
	int i;
	for(i=b[x];up[i].size()!=1;i=b[findUp(i)]) Do(findUp(i),findDown(i));
	for(i=b[y];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;
}

Subtask #1
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14684 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 -

Subtask #2
0.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 83 ms 47252 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 29788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 29788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 14 ms 29788 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 14680 KB Output is correct
2 Correct 3 ms 14684 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 -