oj.uz

Submission #223392

# Submission time Handle Problem Language Result Execution time Memory
223392 2020-04-15T08:36:42 Z errorgorn Matching (COCI20_matching) C++14
5 / 110
 10 ms 5120 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ll,ii>
#define endl '\n'
 
const int MOD=1000000007;
 
int n;
 
ii pos[100005];
vector<int> X[100005];
vector<int> Y[100005];
 
bool visited[100005];
 
deque<int> stk; //bruh
 
void dfs(int i,bool dir){
	//cout<<i<<" "<<dir<<endl;
	visited[i]=true;
	
	if (dir) stk.push_back(i);
	else stk.push_front(i);
	
	for (auto &it:X[pos[i].first]) if (!visited[it]) dfs(it,dir);
	for (auto &it:Y[pos[i].second]) if (!visited[it]) dfs(it,dir);
}

struct comp{
	vector<ii> ansX;
	vector<ii> ansY;
	
	comp(){}
};

vector<comp> comps; //this is so cancer bruh

vector<int> mono;

vector<ii> ans; //real answer now

bool intersect(ii i,ii j){
	if (pos[i.first].first!=pos[i.second].first) swap(i,j);
	if (pos[i.first].second!=pos[i.second].second) return false;
	return !(min(pos[j.first].first,pos[j.second].first)<=pos[i.first].first &&
			max(pos[j.first].first,pos[j.second].first)>=pos[i.first].first &&
			min(pos[i.first].second,pos[i.second].second)<=pos[j.first].second &&
			max(pos[i.first].second,pos[i.second].second)>=pos[j.first].second);
}
 
int main(){	
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin>>n;
	
	int a,b;
	int index=0;
	for (int x=0;x<n;x++){
		cin>>a>>b;
		
		pos[index]=ii(a,b);
		X[a].push_back(index);
		Y[b].push_back(index);
		
		index++;
	}
	
	for (int x=0;x<n;x++){
		if (!visited[x]){
			visited[x]=true;
			stk.clear();
			stk.push_back(x);
			
			for (auto &it:X[pos[x].first]) if (!visited[it]) dfs(it,true);
			for (auto &it:Y[pos[x].second]) if (!visited[it]) dfs(it,false);
			
			if (stk.size()%2==1){
				cout<<"NE"<<endl;
				return 0;
			}
			else{
				comps.push_back(comp());
				if (pos[stk[0]].first==pos[stk[1]].first){
					for (int x=0;x<stk.size();x+=2){
						comps.back().ansX.push_back(ii(stk[x],stk[x+1]));
					}
					if (pos[stk.front()].second==pos[stk.back()].second){
						stk.push_back(stk.front());
						stk.pop_front();
						
						for (int x=0;x<stk.size();x+=2){
							comps.back().ansY.push_back(ii(stk[x],stk[x+1]));
						}
					}
				}
				else{
					for (int x=0;x<stk.size();x+=2){
						comps.back().ansY.push_back(ii(stk[x],stk[x+1]));
					}
					if (pos[stk.front()].first==pos[stk.back()].first){
						stk.push_back(stk.front());
						stk.pop_front();
						
						for (int x=0;x<stk.size();x+=2){
							comps.back().ansX.push_back(ii(stk[x],stk[x+1]));
						}
					}
				}
			}
		}
	}
	
	/*
	for (auto &it:comps){
		cout<<it.ansX.size()<<" "<<it.ansY.size()<<endl;
	}
	*/
	
	for (int x=0;x<comps.size();x++) {
		if (comps[x].ansX.empty() || comps[x].ansY.empty()) mono.push_back(x);
	}
	
	while (!mono.empty()){
		int index=mono.back();
		mono.pop_back();
		
		for (int x=0;x<comps.size();x++){
			if (!(comps[x].ansX.empty() || comps[x].ansY.empty())){
				if (comps[index].ansX.empty()){
					for (auto &it:comps[index].ansY){
						for (auto &it2:comps[x].ansX){
							if (intersect(it,it2)){
								comps[x].ansX.clear();
								mono.push_back(x);
								goto _end;
							}
						}
					}
				}
				else{
					for (auto &it:comps[index].ansX){
						for (auto &it2:comps[x].ansY){
							if (intersect(it,it2)){
								comps[x].ansY.clear();
								mono.push_back(x);
								goto _end;
							}
						}
					}
				}
				
				_end:;
			}
		}
	}
	
	for (auto &it:comps){
		if (it.ansX.empty()) ans.insert(ans.end(),it.ansY.begin(),it.ansY.end());
		else ans.insert(ans.end(),it.ansX.begin(),it.ansX.end());
	}
	
	for (int x=0;x<ans.size();x++){
		for (int y=0;y<ans.size();y++){
			if (intersect(ans[x],ans[y])){
				cout<<"NE"<<endl;
				return 0;
			}
		}
	}
	
	cout<<"DA"<<endl;
	for (auto &it:ans){
		cout<<it.first+1<<" "<<it.second+1<<endl;
	}
}

Compilation message

matching.cpp: In function 'int main()':
matching.cpp:87:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int x=0;x<stk.size();x+=2){
                   ~^~~~~~~~~~~
matching.cpp:94:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int x=0;x<stk.size();x+=2){
                    ~^~~~~~~~~~~
matching.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int x=0;x<stk.size();x+=2){
                   ~^~~~~~~~~~~
matching.cpp:107:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int x=0;x<stk.size();x+=2){
                    ~^~~~~~~~~~~
matching.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<comps.size();x++) {
               ~^~~~~~~~~~~~~
matching.cpp:130:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int x=0;x<comps.size();x++){
                ~^~~~~~~~~~~~~
matching.cpp:165:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int x=0;x<ans.size();x++){
               ~^~~~~~~~~~~
matching.cpp:166:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int y=0;y<ans.size();y++){
                ~^~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Incorrect 10 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Incorrect 10 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Incorrect 10 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB Output is correct
2 Correct 7 ms 4992 KB Output is correct
3 Correct 7 ms 4992 KB Output is correct
4 Correct 7 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Incorrect 10 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -