oj.uz

Submission #463661

# Submission time Handle Problem Language Result Execution time Memory
463661 2021-08-11T12:57:42 Z Jasiekstrz Matching (COCI20_matching) C++17
58 / 110
 2500 ms 223472 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]=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]=-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 45 ms 24916 KB Output is correct
2 Correct 42 ms 24960 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24916 KB Output is correct
2 Correct 42 ms 24960 KB Output is correct
3 Correct 42 ms 24964 KB Output is correct
4 Correct 43 ms 24984 KB Output is correct
5 Correct 42 ms 25016 KB Output is correct
6 Correct 39 ms 24948 KB Output is correct
7 Correct 40 ms 24996 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24916 KB Output is correct
2 Correct 42 ms 24960 KB Output is correct
3 Correct 42 ms 24964 KB Output is correct
4 Correct 43 ms 24984 KB Output is correct
5 Correct 42 ms 25016 KB Output is correct
6 Correct 39 ms 24948 KB Output is correct
7 Correct 40 ms 24996 KB Output is correct
8 Correct 42 ms 24980 KB Output is correct
9 Correct 43 ms 25028 KB Output is correct
10 Correct 44 ms 24996 KB Output is correct
11 Correct 40 ms 25004 KB Output is correct
12 Correct 43 ms 24932 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24916 KB Output is correct
2 Correct 42 ms 24960 KB Output is correct
3 Correct 42 ms 24964 KB Output is correct
4 Correct 43 ms 24984 KB Output is correct
5 Correct 42 ms 25016 KB Output is correct
6 Correct 39 ms 24948 KB Output is correct
7 Correct 40 ms 24996 KB Output is correct
8 Correct 42 ms 24980 KB Output is correct
9 Correct 43 ms 25028 KB Output is correct
10 Correct 44 ms 24996 KB Output is correct
11 Correct 40 ms 25004 KB Output is correct
12 Correct 43 ms 24932 KB Output is correct
13 Correct 50 ms 26408 KB Output is correct
14 Correct 53 ms 26360 KB Output is correct
15 Correct 52 ms 26520 KB Output is correct
16 Correct 52 ms 26320 KB Output is correct
17 Correct 51 ms 26628 KB Output is correct
18 Correct 58 ms 26384 KB Output is correct
19 Correct 51 ms 26232 KB Output is correct
20 Correct 50 ms 26180 KB Output is correct
21 Correct 48 ms 26220 KB Output is correct
22 Correct 49 ms 26632 KB Output is correct
23 Correct 51 ms 26296 KB Output is correct
24 Correct 46 ms 26400 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 24916 KB Output is correct
2 Correct 42 ms 24960 KB Output is correct
3 Correct 42 ms 24964 KB Output is correct
4 Correct 43 ms 24984 KB Output is correct
5 Correct 42 ms 25016 KB Output is correct
6 Correct 39 ms 24948 KB Output is correct
7 Correct 40 ms 24996 KB Output is correct
8 Correct 42 ms 24980 KB Output is correct
9 Correct 43 ms 25028 KB Output is correct
10 Correct 44 ms 24996 KB Output is correct
11 Correct 40 ms 25004 KB Output is correct
12 Correct 43 ms 24932 KB Output is correct
13 Correct 50 ms 26408 KB Output is correct
14 Correct 53 ms 26360 KB Output is correct
15 Correct 52 ms 26520 KB Output is correct
16 Correct 52 ms 26320 KB Output is correct
17 Correct 51 ms 26628 KB Output is correct
18 Correct 58 ms 26384 KB Output is correct
19 Correct 51 ms 26232 KB Output is correct
20 Correct 50 ms 26180 KB Output is correct
21 Correct 48 ms 26220 KB Output is correct
22 Correct 49 ms 26632 KB Output is correct
23 Correct 51 ms 26296 KB Output is correct
24 Correct 46 ms 26400 KB Output is correct
25 Correct 856 ms 127832 KB Output is correct
26 Correct 917 ms 131156 KB Output is correct
27 Correct 815 ms 116420 KB Output is correct
28 Correct 822 ms 119384 KB Output is correct
29 Correct 782 ms 121372 KB Output is correct
30 Correct 811 ms 127284 KB Output is correct
31 Correct 758 ms 121336 KB Output is correct
32 Correct 813 ms 121732 KB Output is correct
33 Correct 760 ms 123996 KB Output is correct
34 Correct 721 ms 115056 KB Output is correct
35 Correct 84 ms 23752 KB Output is correct
36 Execution timed out 2533 ms 223472 KB Time limit exceeded
37 Halted 0 ms 0 KB -