oj.uz

Submission #350038

# Submission time Handle Problem Language Result Execution time Memory
350038 2021-01-18T23:22:19 Z arnold518 Matching (COCI20_matching) C++14
11 / 110
 163 ms 240108 KB 
#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 = 5e6;

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<int> adj[MAXM+10], radj[MAXM+10];

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

int scc[MAXM+10], scnt;
void dfs2(int now)
{
	scc[now]=scnt;
	for(int nxt : radj[now])
	{
		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[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])
		{
			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);	
			}
		}
	}

	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

matching.cpp: In function 'int update(int, int, int, int, int)':
matching.cpp:62:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |  int mid=tl+tr>>1;
      |          ~~^~~
matching.cpp: In function 'void query(int, int, int, int, int, int)':
matching.cpp:78:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int mid=tl+tr>>1;
      |          ~~^~~
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: In function 'int main()':
matching.cpp:246:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  246 |  assert(ans.size()==N);
      |         ~~~~~~~~~~^~~
matching.cpp:249:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  249 |  assert(ans.size()==N);
      |         ~~~~~~~~~~^~~
matching.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
matching.cpp:88:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%d%d", &A[i].first, &A[i].second);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 239980 KB Output is correct
2 Correct 162 ms 239980 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 239980 KB Output is correct
2 Correct 162 ms 239980 KB Output is correct
3 Correct 163 ms 239960 KB Output is correct
4 Correct 163 ms 239980 KB Output is correct
5 Correct 162 ms 239980 KB Output is correct
6 Correct 163 ms 239980 KB Output is correct
7 Correct 162 ms 240108 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 239980 KB Output is correct
2 Correct 162 ms 239980 KB Output is correct
3 Correct 163 ms 239960 KB Output is correct
4 Correct 163 ms 239980 KB Output is correct
5 Correct 162 ms 239980 KB Output is correct
6 Correct 163 ms 239980 KB Output is correct
7 Correct 162 ms 240108 KB Output is correct
8 Correct 162 ms 239980 KB Output is correct
9 Incorrect 162 ms 240108 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 239980 KB Output is correct
2 Correct 162 ms 239980 KB Output is correct
3 Correct 163 ms 239960 KB Output is correct
4 Correct 163 ms 239980 KB Output is correct
5 Correct 162 ms 239980 KB Output is correct
6 Correct 163 ms 239980 KB Output is correct
7 Correct 162 ms 240108 KB Output is correct
8 Correct 162 ms 239980 KB Output is correct
9 Incorrect 162 ms 240108 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 239980 KB Output is correct
2 Correct 162 ms 239980 KB Output is correct
3 Correct 163 ms 239960 KB Output is correct
4 Correct 163 ms 239980 KB Output is correct
5 Correct 162 ms 239980 KB Output is correct
6 Correct 163 ms 239980 KB Output is correct
7 Correct 162 ms 240108 KB Output is correct
8 Correct 162 ms 239980 KB Output is correct
9 Incorrect 162 ms 240108 KB Output isn't correct
10 Halted 0 ms 0 KB -