oj.uz

Submission #463656

# Submission time Handle Problem Language Result Execution time Memory
463656 2021-08-11T12:49:47 Z Jasiekstrz Matching (COCI20_matching) C++17
58 / 110
 2500 ms 332976 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];

// 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 59800 KB Output is correct
2 Correct 141 ms 59840 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 59800 KB Output is correct
2 Correct 141 ms 59840 KB Output is correct
3 Correct 141 ms 59764 KB Output is correct
4 Correct 144 ms 59804 KB Output is correct
5 Correct 151 ms 59900 KB Output is correct
6 Correct 135 ms 59772 KB Output is correct
7 Correct 140 ms 59776 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 59800 KB Output is correct
2 Correct 141 ms 59840 KB Output is correct
3 Correct 141 ms 59764 KB Output is correct
4 Correct 144 ms 59804 KB Output is correct
5 Correct 151 ms 59900 KB Output is correct
6 Correct 135 ms 59772 KB Output is correct
7 Correct 140 ms 59776 KB Output is correct
8 Correct 141 ms 59900 KB Output is correct
9 Correct 149 ms 59988 KB Output is correct
10 Correct 151 ms 59900 KB Output is correct
11 Correct 149 ms 59912 KB Output is correct
12 Correct 168 ms 59896 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 59800 KB Output is correct
2 Correct 141 ms 59840 KB Output is correct
3 Correct 141 ms 59764 KB Output is correct
4 Correct 144 ms 59804 KB Output is correct
5 Correct 151 ms 59900 KB Output is correct
6 Correct 135 ms 59772 KB Output is correct
7 Correct 140 ms 59776 KB Output is correct
8 Correct 141 ms 59900 KB Output is correct
9 Correct 149 ms 59988 KB Output is correct
10 Correct 151 ms 59900 KB Output is correct
11 Correct 149 ms 59912 KB Output is correct
12 Correct 168 ms 59896 KB Output is correct
13 Correct 189 ms 65272 KB Output is correct
14 Correct 185 ms 65500 KB Output is correct
15 Correct 186 ms 65312 KB Output is correct
16 Correct 186 ms 65348 KB Output is correct
17 Correct 188 ms 65388 KB Output is correct
18 Correct 188 ms 65268 KB Output is correct
19 Correct 198 ms 65376 KB Output is correct
20 Correct 183 ms 65296 KB Output is correct
21 Correct 181 ms 65300 KB Output is correct
22 Correct 209 ms 65332 KB Output is correct
23 Correct 208 ms 65328 KB Output is correct
24 Correct 171 ms 65272 KB Output is correct

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 59800 KB Output is correct
2 Correct 141 ms 59840 KB Output is correct
3 Correct 141 ms 59764 KB Output is correct
4 Correct 144 ms 59804 KB Output is correct
5 Correct 151 ms 59900 KB Output is correct
6 Correct 135 ms 59772 KB Output is correct
7 Correct 140 ms 59776 KB Output is correct
8 Correct 141 ms 59900 KB Output is correct
9 Correct 149 ms 59988 KB Output is correct
10 Correct 151 ms 59900 KB Output is correct
11 Correct 149 ms 59912 KB Output is correct
12 Correct 168 ms 59896 KB Output is correct
13 Correct 189 ms 65272 KB Output is correct
14 Correct 185 ms 65500 KB Output is correct
15 Correct 186 ms 65312 KB Output is correct
16 Correct 186 ms 65348 KB Output is correct
17 Correct 188 ms 65388 KB Output is correct
18 Correct 188 ms 65268 KB Output is correct
19 Correct 198 ms 65376 KB Output is correct
20 Correct 183 ms 65296 KB Output is correct
21 Correct 181 ms 65300 KB Output is correct
22 Correct 209 ms 65332 KB Output is correct
23 Correct 208 ms 65328 KB Output is correct
24 Correct 171 ms 65272 KB Output is correct
25 Correct 2088 ms 332460 KB Output is correct
26 Correct 2185 ms 332976 KB Output is correct
27 Correct 2094 ms 332956 KB Output is correct
28 Correct 2099 ms 332444 KB Output is correct
29 Correct 2049 ms 332484 KB Output is correct
30 Correct 2118 ms 332272 KB Output is correct
31 Correct 2066 ms 332572 KB Output is correct
32 Correct 2102 ms 332000 KB Output is correct
33 Correct 1972 ms 306692 KB Output is correct
34 Correct 1908 ms 306304 KB Output is correct
35 Correct 107 ms 23940 KB Output is correct
36 Execution timed out 2605 ms 302560 KB Time limit exceeded
37 Halted 0 ms 0 KB -