Submission #350040

#	Time	Username	Problem	Language	Result	Execution time	Memory
350040		arnold518	Matching (COCI20_matching)	C++14	110 / 110	2393 ms	231208 KiB

matching

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;
const int MAXM = 6e6;

int N, M, M1, M2;
pii A[MAXN+10];
vector<int> X[MAXN+10], Y[MAXN+10];
int P[MAXN+10], Q[MAXN+10];
pii E[MAXN*2+10];

vector<pii> adj, radj;
int idx[MAXM+10], ridx[MAXM+10];

bool vis[MAXM+10];
vector<int> S;
void dfs(int now)
{
	vis[now]=true;
	for(int i=idx[now]; i<idx[now+1]; i++)
	{
		int nxt=adj[i].second;
		if(vis[nxt]) continue;
		dfs(nxt);
	}
	S.push_back(now);
}

int scc[MAXM+10], scnt;
void dfs2(int now)
{
	scc[now]=scnt;
	for(int i=ridx[now]; i<ridx[now+1]; i++)
	{
		int nxt=radj[i].second;
		if(scc[nxt]) continue;
		dfs2(nxt);
	}
}

void addEdge(int u, int v)
{
	if(u==0 || v==0) return;
	//printf("%d %d\n", u, v);
	adj.push_back({u, v});
	radj.push_back({v, u});
	//adj[u].push_back(v);
	//radj[v].push_back(u);
}

pii nodes[MAXM+10];

int update(int node, int tl, int tr, int p, int k)
{
	if(p<tl || tr<p) return node;
	int ret=++M;
	if(tl==tr)
	{
		addEdge(ret, k);
		return ret;
	}
	int mid=tl+tr>>1;
	nodes[ret]={update(nodes[node].first, tl, mid, p, k), update(nodes[node].second, mid+1, tr, p, k)};
	addEdge(ret, nodes[ret].first);
	addEdge(ret, nodes[ret].second);
	return ret;
}

void query(int node, int tl, int tr, int l, int r, int k)
{
	if(node==0) return;
	if(r<tl || tr<l) return;
	if(l<=tl && tr<=r)
	{
		addEdge(k, node);
		return;
	}
	int mid=tl+tr>>1;
	query(nodes[node].first, tl, mid, l, r, k);
	query(nodes[node].second, mid+1, tr, l, r, k);
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].first, &A[i].second);
		X[A[i].first].push_back(i);
		Y[A[i].second].push_back(i);
	}

	for(int i=1; i<=MAXN; i++)
	{
		if(X[i].size()==2)
		{
			M++;
			if(A[X[i][0]]>A[X[i][1]]) swap(X[i][0], X[i][1]);
			E[M]={X[i][0], X[i][1]};
			P[X[i][0]]=M;
			P[X[i][1]]=M;
		}
	}
	M1=M;
	for(int i=1; i<=MAXN; i++)
	{
		if(Y[i].size()==2)
		{
			M++;
			if(A[Y[i][0]]>A[Y[i][1]]) swap(Y[i][0], Y[i][1]);
			E[M]={Y[i][0], Y[i][1]};
			Q[Y[i][0]]=M;
			Q[Y[i][1]]=M;
		}
	}
	M2=M;

	for(int i=1; i<=N; i++)
	{
		if(P[i]==0 && Q[i]==0) 
		{
			return !printf("NE\n");
		}
		if(P[i] && Q[i])
		{
			addEdge(P[i]+M2, Q[i]);
			addEdge(P[i], Q[i]+M2);
			addEdge(Q[i]+M2, P[i]);
			addEdge(Q[i], P[i]+M2);
		}
		else if(P[i])
		{
			addEdge(P[i]+M2, P[i]);
		}
		else if(Q[i])
		{
			addEdge(Q[i]+M2, Q[i]);
		}
	}
	M*=2;

/*
	for(int i=1; i<=M1; i++) for(int j=M1+1; j<=M2; j++)
	{
		if(A[E[i].first].second<=A[E[j].first].second && A[E[j].second].second<=A[E[i].second].second)
		{
			if(A[E[j].first].first<=A[E[i].first].first && A[E[i].second].first<=A[E[j].second].first)
			{
				addEdge(i, j+M2);
				addEdge(j, i+M2);
			}	
		}
	}
*/

	vector<pii> V;
	for(int i=1; i<=M1; i++)
	{
		V.push_back({A[E[i].first].second, i});
		V.push_back({A[E[i].second].second+1, -i});
	}

	for(int i=M1+1; i<=M2; i++)
	{
		V.push_back({A[E[i].first].second, i});
	}
	sort(V.begin(), V.end());

	int root=++M;
	for(auto it : V)
	{
		if(it.second>=M1+1)
		{
			query(root, 1, MAXN, A[E[it.second].first].first, A[E[it.second].second].first, it.second);
		}
		else
		{
			if(it.second>=0)
			{
				root=update(root, 1, MAXN, A[E[it.second].first].first, it.second+M2);
			}
			else
			{
				root=update(root, 1, MAXN, A[E[-it.second].first].first, 0);	
			}
		}
	}

	V.clear();
	for(int i=M1+1; i<=M2; i++)
	{
		V.push_back({A[E[i].first].first, i});
		V.push_back({A[E[i].second].first+1, -i});
	}

	for(int i=1; i<=M1; i++)
	{
		V.push_back({A[E[i].first].first, i+M2});
	}
	sort(V.begin(), V.end());

	root=++M;
	for(auto it : V)
	{
		if(it.second>=M2+1)
		{
			query(root, 1, MAXN, A[E[it.second-M2].first].second, A[E[it.second-M2].second].second, it.second-M2);
		}
		else
		{
			if(it.second>=0)
			{
				root=update(root, 1, MAXN, A[E[it.second].first].second, it.second+M2);
			}
			else
			{
				root=update(root, 1, MAXN, A[E[-it.second].first].second, 0);	
			}
		}
	}

	sort(adj.begin(), adj.end());
	sort(radj.begin(), radj.end());

	for(int i=0, j=1; i<adj.size(); i++)
	{
		for(; j<=adj[i].first; j++) idx[j]=i;
	}
	idx[M+1]=adj.size();

	for(int i=0, j=1; i<radj.size(); i++)
	{
		for(; j<=radj[i].first; j++) ridx[j]=i;
	}
	ridx[M+1]=radj.size();

	for(int i=1; i<=M; i++) if(!vis[i]) dfs(i);
	reverse(S.begin(), S.end());
	for(auto it : S)
	{
		if(scc[it]) continue;
		scnt++;
		dfs2(it);
	}

	for(int i=1; i<=M2; i++)
	{
		//printf("%d %d\n", E[i].first, E[i].second);
		//printf("%d %d\n", scc[i], scc[i+M2]);
		if(scc[i]==scc[i+M2])
		{
			return !printf("NE\n");
		}
	}

	printf("DA\n");
	vector<int> ans;
	for(int i=1; i<=M2; i++)
	{
		if(scc[i]>scc[i+M2])
		{
			printf("%d %d\n", E[i].first, E[i].second);
			ans.push_back(E[i].first);
			ans.push_back(E[i].second);
		}
	}

	assert(ans.size()==N);
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	assert(ans.size()==N);
}

Compilation message (stderr)

matching.cpp: In function 'int update(int, int, int, int, int)':
matching.cpp:67:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |  int mid=tl+tr>>1;
      |          ~~^~~
matching.cpp: In function 'void query(int, int, int, int, int, int)':
matching.cpp:83:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |  int mid=tl+tr>>1;
      |          ~~^~~
matching.cpp: In function 'int main()':
matching.cpp:230:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |  for(int i=0, j=1; i<adj.size(); i++)
      |                    ~^~~~~~~~~~~
matching.cpp:236:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  236 |  for(int i=0, j=1; i<radj.size(); i++)
      |                    ~^~~~~~~~~~~~
In file included from /usr/include/c++/9/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
                 from matching.cpp:1:
matching.cpp:273:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  273 |  assert(ans.size()==N);
      |         ~~~~~~~~~~^~~
matching.cpp:276:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  276 |  assert(ans.size()==N);
      |         ~~~~~~~~~~^~~
matching.cpp:90:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
matching.cpp:93:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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