제출 #1045467

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1045467		moonrabbit2	Parking (CEOI22_parking)	C++17	100 / 100	332 ms	42348 KiB

Main

#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);
	sort(nl.begin(),nl.end());
	nl.resize(unique(nl.begin(),nl.end())-nl.begin());
	for(int c: l[i]) if(b[c]==t[c]) 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){
	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];
		t[x]=0;
	} else{
		assert(!b[y]||b[x]==b[y]);
		if(!b[y]) b[y]=b[x];
		else t[y]=b[x];
		b[x]=0;
	}
	if(b[x]) upd(b[x]);
	if(t[x]) upd(t[x]);
	if(b[y]) upd(b[y]);
	if(t[y]) upd(t[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(){
	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);
	assert(up[s].size()==1);
	for(int s=0;s<(int)V.size();){
		int e1=s,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];
		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(),x=l[i][0],y=l[i][1];
	Do(x,y);
	e.push_back(x);
}
void solveCycle(){
	if(!outcnt){
		if(e.empty()) fail();
		int s=V[0],x=b[findUp(s)];
		V.clear();
		while(x!=s){
			V.push_back(x);
			x=b[findUp(x)];
		}
		x=findUp(s);
		Do(x,e[0]);
		for(int u: V) Do(findUp(u),findDown(u));
		Do(e[0],findDown(s));
		return;
	}
	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],j;i!=t;i=j){
			j=b[findUp(i)];
			Do(findUp(i),findDown(i));
		}
		for(int i=b[y],j;i!=t;i=j){
			j=b[findUp(i)];
			Do(findUp(i),findDown(i));
		}
		x=l[t][0],y=l[t][1];
		Do(x,y);
		e[0]=x;
		return;
	}
	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(int i=b[x],j;up[i].size()!=1;i=j){
		j=b[findUp(i)];
		Do(findUp(i),findDown(i));
	}
	for(int i=b[y],j;up[i].size()!=1;i=j){
		j=b[findUp(i)];
		Do(findUp(i),findDown(i));
	}
	for(int u: V){
		vis[u]=0;
		if(l[u][0]!=l[u][1]) s=u;
	}
	V.clear();
	dfs(s);
	solvePath();
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	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;
}

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

Main.cpp: In function 'void solveCycle()':
Main.cpp:157:6: warning: unused variable 'i' [-Wunused-variable]
  157 |  int i;
      |      ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 15 / 15
• Subtask 5: 25 / 25
• Subtask 6: 15 / 15