Submission #463656

#	Time	Username	Problem	Language	Result	Execution time	Memory
463656		Jasiekstrz	Matching (COCI20_matching)	C++17	58 / 110	2605 ms	332976 KiB

matching

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
const int PP=(1<<17);
//#warning small constants
//const int N=4;
//const int PP=4;
pair<int,int> tab[N+10];
vector<int> cup[2][N+10];
int cnt[N+10];
int tree[2*PP+10];

// sat
// 2*id - var, 2*id+1 - !var
int var[2][N+10];
int neg(int x)
{
	return (x%2==0 ? x+1:x-1);
}
vector<vector<int>> e;
int new_var()
{
	for(int i:{0,1})
		e.push_back({});
	return e.size()-2;
}
void new_clause(int a,int b)
{
	//auto debwr=[](int x){ if(x%2==0) cerr<<x<<" "; else cerr<<"!"<<x-1<<" "; return; };
	//debwr(a); cerr<<"or "; debwr(b); cerr<<"\n";

	e[neg(a)].push_back(b);
	e[neg(b)].push_back(a);
	return;
}
vector<int> low;
vector<int> pre;
vector<bool> val;
vector<bool> vis;
vector<bool> on_stack;
vector<int> scc;
vector<int> stck;
vector<int> topo;
void dfs1(int x)
{
	static int nr=0,sccnr=0;
	vis[x]=true;
	stck.push_back(x);
	on_stack[x]=true;
	pre[x]=nr++;
	low[x]=pre[x];
	for(auto v:e[x])
	{
		if(on_stack[v])
			low[x]=min(low[x],pre[v]);
		else if(!vis[v])
		{
			dfs1(v);
			low[x]=min(low[x],low[v]);
		}
	}
	if(low[x]==pre[x])
	{
		while(on_stack[x])
		{
			int v=stck.back();
			stck.pop_back();
			scc[v]=sccnr;
			on_stack[v]=false;
		}
		sccnr++;
	}
	return;
}
void dfs2(int x)
{
	vis[x]=true;
	for(auto v:e[x])
	{
		if(!vis[v])
			dfs2(v);
	}
	if(low[x]==pre[x])
		topo.push_back(x);
	return;
}
void dfs3(int x)
{
	vis[x]=true;
	val[scc[neg(x)]]=!val[scc[x]];
	for(auto v:e[x])
	{
		if(!vis[v])
		{
			if(scc[v]==scc[x])
				dfs3(v);
			else if(val[scc[x]])
				val[scc[v]]=true;
		}
	}
	return;
}
vector<bool> solve_2sat()
{
	int n=e.size();
	for(auto *vec:{&low,&pre,&scc})
		vec->resize(n);
	for(auto *vec:{&val,&vis,&on_stack})
	{
		vec->resize(n);
		fill(vec->begin(),vec->end(),false);
	}
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
			dfs1(i);
	}
	fill(vis.begin(),vis.end(),false);
	for(int i=0;i<n;i++)
	{
		if(!vis[i])
			dfs2(i);
	}
	reverse(topo.begin(),topo.end());
	fill(vis.begin(),vis.end(),false);
	for(auto v:topo)
	{
		dfs3(v);
	}

	//for(int i=0;i<n;i++)
	//	cerr<<"scc["<<i<<"]="<<scc[i]<<" "<<val[scc[i]]<<"\n";

	vector<bool> ans(n,false);
	for(int i=0;i<n;i++)
	{
		if(val[scc[i]]==val[scc[neg(i)]])
			return {};
		for(auto v:e[i])
		{
			if(val[scc[i]] && !val[scc[v]])
				return {};
		}
		ans[i]=val[scc[i]];
	}
	return ans;
}

void new_node(int x)
{
	tree[x]=new_var();
	new_clause(neg(tree[2*x]),tree[x]);
	new_clause(neg(tree[2*x+1]),tree[x]);
	return;
}
void add_segment(int l,int r,int c)
{
	for(l+=PP-1,r+=PP-1;l<=r;l/=2,r/=2)
	{
		if(l%2==1)
			new_clause(neg(c),neg(tree[l++]));
		if(r%2==0)
			new_clause(neg(c),neg(tree[r--]));
	}
	return;
}
void upd_node(int x,int c)
{
	x+=PP-1;
	tree[x]=c;
	for(x/=2;x>0;x/=2)
		new_node(x);
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>tab[i].fi>>tab[i].se;
		cup[0][tab[i].fi].push_back(i);
		cup[1][tab[i].se].push_back(i);
	}
	for(int i=1;i<=N;i++)
	{
		var[0][i]=new_var();
		var[1][i]=new_var();
	}
	for(int i=1;i<=n;i++)
	{
		if(cup[0][tab[i].fi].size()==1 && cup[1][tab[i].se].size()==1)
		{
			cout<<"NE\n";
			return 0;
		}
		else if(cup[0][tab[i].fi].size()==1)
			new_clause(var[1][tab[i].se],var[1][tab[i].se]);
		else if(cup[1][tab[i].se].size()==1)
			new_clause(var[0][tab[i].fi],var[0][tab[i].fi]);
		else
		{
			new_clause(var[0][tab[i].fi],var[1][tab[i].se]);
			new_clause(neg(var[0][tab[i].fi]),neg(var[1][tab[i].se]));
		}
	}
	for(int i=PP;i<2*PP;i++)
		tree[i]=new_var();
	for(int i=PP-1;i>0;i--)
		new_node(i);
	for(int i=1;i<=N;i++)
	{
		if(cup[1][i].size()==2)
		{
			int l=cup[1][i][0],r=cup[1][i][1];
			l=tab[l].fi;
			r=tab[r].fi;
			if(l>r)
				swap(l,r);
			add_segment(l,r,var[1][i]);
		}
		for(auto v:cup[1][i])
		{
			v=tab[v].fi;
			if(cnt[v]==0)
				upd_node(v,var[0][v]);
			else
				upd_node(v,new_var());
			cnt[v]++;
		}
	}

	//for(int i=1;i<=N;i++)
	//{
	//	cerr<<"fi="<<i<<": "<<var[0][i]<<"\n";
	//	cerr<<"se="<<i<<": "<<var[1][i]<<"\n";
	//}

	auto ans=solve_2sat();
	if(ans.empty())
	{
		cout<<"NE\n";
		return 0;
	}
	cout<<"DA\n";
	for(int i=1;i<=N;i++)
	{
		for(int j:{0,1})
		{
			if(cup[j][i].size()==2 && ans[var[j][i]])
				cout<<cup[j][i][0]<<" "<<cup[j][i][1]<<"\n";
		}
	}
	return 0;
}

Compilation message (stderr)

matching.cpp: In function 'int new_var()':
matching.cpp:25:10: warning: unused variable 'i' [-Wunused-variable]
   25 |  for(int i:{0,1})
      |          ^

• Subtask 1: 5 / 5
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 40 / 40
• Subtask 5: 0 / 52