oj.uz

Submission #1044343

# Submission time Handle Problem Language Result Execution time Memory
1044343 2024-08-05T08:57:54 Z ㅇㅇ(#11061) Parking (CEOI22_parking) C++17
20 / 100
 68 ms 29788 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);
	sort(nl.begin(),nl.end());
	nl.resize(unique(nl.begin(),nl.end())-nl.begin());
	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];
		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;
	//debug(u,g[u]);
	isCyc&=g[u].size()==2;
	//debug(u,isCyc);
	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");
	//debug("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);
	assert(up[s].size()==1);
	/*debug(up[V.back()]);
	debug(V);
	for(int u: V){
		debug(l[u],g[u]);
		for(int c: l[u]) debug(b[c],t[c]);
	}*/
	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];
		//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");
	//debug("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));
		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];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;
		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(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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 14680 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14680 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 24524 KB Output is correct
2 Correct 68 ms 26836 KB Output is correct
3 Correct 38 ms 22472 KB Output is correct
4 Correct 45 ms 21964 KB Output is correct
5 Correct 61 ms 26684 KB Output is correct

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 29788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 29788 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 29788 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14680 KB Output is correct
3 Correct 2 ms 14680 KB Output is correct
4 Correct 2 ms 14680 KB Output is correct
5 Correct 2 ms 14684 KB Output is correct
6 Correct 2 ms 14680 KB Output is correct
7 Correct 2 ms 14684 KB Output is correct
8 Correct 2 ms 14684 KB Output is correct
9 Correct 2 ms 14684 KB Output is correct
10 Correct 2 ms 14684 KB Output is correct
11 Correct 56 ms 24524 KB Output is correct
12 Correct 68 ms 26836 KB Output is correct
13 Correct 38 ms 22472 KB Output is correct
14 Correct 45 ms 21964 KB Output is correct
15 Correct 61 ms 26684 KB Output is correct
16 Runtime error 10 ms 29788 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -