oj.uz

Submission #463663

# Submission time Handle Problem Language Result Execution time Memory
463663 2021-08-11T13:03:03 Z Jasiekstrz Matching (COCI20_matching) C++17
110 / 110
 2491 ms 209648 KB 
#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];
bool ok[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)
{
	if(!ok[2*x] && !ok[2*x+1])
	{
		ok[x]=false;
		tree[x]=-1;
		return;
	}
	ok[x]=true;
	if(!ok[2*x])
	{
		tree[x]=tree[2*x+1];
		return;
	}
	if(!ok[2*x+1])
	{
		tree[x]=tree[2*x];
		return;
	}
	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)
		{
			if(ok[l])
				new_clause(neg(c),neg(tree[l]));
			l++;
		}
		if(r%2==0)
		{
			if(ok[r])
				new_clause(neg(c),neg(tree[r]));
			r--;
		}
	}
	return;
}
void upd_node(int x,int c)
{
	x+=PP-1;
	ok[x]=(c!=-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]=-1;
		var[1][i]=-1;
	}
	for(int i=1;i<=n;i++)
	{
		if(var[0][tab[i].fi]==-1)
			var[0][tab[i].fi]=new_var();
		if(var[1][tab[i].se]==-1)
			var[1][tab[i].se]=new_var();
		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]=-1;
		ok[i]=false;
	}
	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,-1);
			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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7116 KB Output is correct
2 Correct 6 ms 7116 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7116 KB Output is correct
2 Correct 6 ms 7116 KB Output is correct
3 Correct 6 ms 7116 KB Output is correct
4 Correct 6 ms 7116 KB Output is correct
5 Correct 6 ms 7116 KB Output is correct
6 Correct 5 ms 7132 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7116 KB Output is correct
2 Correct 6 ms 7116 KB Output is correct
3 Correct 6 ms 7116 KB Output is correct
4 Correct 6 ms 7116 KB Output is correct
5 Correct 6 ms 7116 KB Output is correct
6 Correct 5 ms 7132 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct
8 Correct 6 ms 7116 KB Output is correct
9 Correct 6 ms 7116 KB Output is correct
10 Correct 6 ms 7116 KB Output is correct
11 Correct 5 ms 7116 KB Output is correct
12 Correct 6 ms 7116 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7116 KB Output is correct
2 Correct 6 ms 7116 KB Output is correct
3 Correct 6 ms 7116 KB Output is correct
4 Correct 6 ms 7116 KB Output is correct
5 Correct 6 ms 7116 KB Output is correct
6 Correct 5 ms 7132 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct
8 Correct 6 ms 7116 KB Output is correct
9 Correct 6 ms 7116 KB Output is correct
10 Correct 6 ms 7116 KB Output is correct
11 Correct 5 ms 7116 KB Output is correct
12 Correct 6 ms 7116 KB Output is correct
13 Correct 12 ms 8704 KB Output is correct
14 Correct 12 ms 8844 KB Output is correct
15 Correct 13 ms 8964 KB Output is correct
16 Correct 12 ms 8604 KB Output is correct
17 Correct 13 ms 8964 KB Output is correct
18 Correct 16 ms 8768 KB Output is correct
19 Correct 12 ms 8576 KB Output is correct
20 Correct 12 ms 8584 KB Output is correct
21 Correct 11 ms 8584 KB Output is correct
22 Correct 13 ms 8992 KB Output is correct
23 Correct 12 ms 8584 KB Output is correct
24 Correct 12 ms 8708 KB Output is correct

Subtask #5
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7116 KB Output is correct
2 Correct 6 ms 7116 KB Output is correct
3 Correct 6 ms 7116 KB Output is correct
4 Correct 6 ms 7116 KB Output is correct
5 Correct 6 ms 7116 KB Output is correct
6 Correct 5 ms 7132 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct
8 Correct 6 ms 7116 KB Output is correct
9 Correct 6 ms 7116 KB Output is correct
10 Correct 6 ms 7116 KB Output is correct
11 Correct 5 ms 7116 KB Output is correct
12 Correct 6 ms 7116 KB Output is correct
13 Correct 12 ms 8704 KB Output is correct
14 Correct 12 ms 8844 KB Output is correct
15 Correct 13 ms 8964 KB Output is correct
16 Correct 12 ms 8604 KB Output is correct
17 Correct 13 ms 8964 KB Output is correct
18 Correct 16 ms 8768 KB Output is correct
19 Correct 12 ms 8576 KB Output is correct
20 Correct 12 ms 8584 KB Output is correct
21 Correct 11 ms 8584 KB Output is correct
22 Correct 13 ms 8992 KB Output is correct
23 Correct 12 ms 8584 KB Output is correct
24 Correct 12 ms 8708 KB Output is correct
25 Correct 941 ms 114964 KB Output is correct
26 Correct 921 ms 122028 KB Output is correct
27 Correct 863 ms 103228 KB Output is correct
28 Correct 837 ms 106596 KB Output is correct
29 Correct 801 ms 108176 KB Output is correct
30 Correct 813 ms 114056 KB Output is correct
31 Correct 780 ms 108056 KB Output is correct
32 Correct 831 ms 109076 KB Output is correct
33 Correct 764 ms 110244 KB Output is correct
34 Correct 740 ms 101520 KB Output is correct
35 Correct 71 ms 19572 KB Output is correct
36 Correct 2491 ms 209648 KB Output is correct
37 Correct 703 ms 93324 KB Output is correct
38 Correct 656 ms 94740 KB Output is correct