oj.uz

Submission #223248

# Submission time Handle Problem Language Result Execution time Memory
223248 2020-04-15T06:12:39 Z errorgorn Matching (COCI20_matching) C++14
5 / 110
 8 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
vector<ii> ansX;
vector<ii> ansY;

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);
}

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{
				if (pos[stk[0]].first==pos[stk[1]].first){
					for (int x=0;x<stk.size();x+=2){
						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){
							ansY.push_back(ii(stk[x],stk[x+1]));
						}
					}
				}
				else{
					for (int x=0;x<stk.size();x+=2){
						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){
							ansX.push_back(ii(stk[x],stk[x+1]));
						}
					}
				}
			}
		}
	}
	
	//cout<<ansX.size()<<" "<<ansY.size()<<endl;
	if (ansX.size()==n/2){
		cout<<"DA"<<endl;
		for (auto &it:ansX){
			cout<<it.first+1<<" "<<it.second+1<<endl;
		}
	}
	else if (ansY.size()==n/2){
		cout<<"DA"<<endl;
		for (auto &it:ansY){
			cout<<it.first+1<<" "<<it.second+1<<endl;
		}
	}
	else{
		cout<<"NE"<<endl;
	}
}

Compilation message

matching.cpp: In function 'int main()':
matching.cpp:66:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int x=0;x<stk.size();x+=2){
                   ~^~~~~~~~~~~
matching.cpp:74:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int x=0;x<stk.size();x+=2){
                    ~^~~~~~~~~~~
matching.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      for (int x=0;x<stk.size();x+=2){
                   ~^~~~~~~~~~~
matching.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for (int x=0;x<stk.size();x+=2){
                    ~^~~~~~~~~~~
matching.cpp:98:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ansX.size()==n/2){
      ~~~~~~~~~~~^~~~~
matching.cpp:104:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  else if (ansY.size()==n/2){
           ~~~~~~~~~~~^~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 6.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 40.0

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

Subtask #5
0 / 52.0

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