oj.uz

Submission #1044191

# Submission time Handle Problem Language Result Execution time Memory
1044191 2024-08-05T07:56:16 Z ㅇㅇ(#11061) Parking (CEOI22_parking) C++17
0 / 100
 48 ms 44848 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,isCirc;
vector<pii> ans;
vector<vector<int>> paths,cycles;
void fail(){
	cout<<"-1\n";
	exit(0);
}
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;
	isCirc&=up[u].size()==1;
	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(){
	assert(0);
	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);
}
void solveCycle(){
	if(isCirc){
		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);
		ans.push_back({x,e[0]});
		for(int u: V) ans.push_back({findUp(u),findDown(u)});
	}
	assert(0);
	if(e.size()<=1) fail();
}
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]){
			ans.push_back({y,x});
			t[x]=i;
			b[y]=0;
			e.push_back(y);
		} else{
			if(t[x]) swap(x,y);
			ans.push_back({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=isCirc=true;
		dfs(s);
		if(!isCyc) solvePath();
		else solveCycle();
	}
	cout<<ans.size()<<"\n";
	for(auto [x,y]: ans) cout<<x<<" "<<y<<"\n";
	return 0;
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 11 ms 29528 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

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

Subtask #4
0.0 / 15.0

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

Subtask #5
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 19 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 3 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 11 ms 29528 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -