Submission #223242

#	Time	Username	Problem	Language	Result	Execution time	Memory
223242		errorgorn	Matching (COCI20_matching)	C++14	5 / 110	8 ms	5120 KiB

matching

#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> ans;

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

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int x=0;x<stk.size();x+=2){
                  ~^~~~~~~~~~~

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