oj.uz

Submission #223245

# Submission time Handle Problem Language Result Execution time Memory
223245 2020-04-15T06:07:22 Z errorgorn Matching (COCI20_matching) C++14
5 / 110
 7 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> 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{
				if (pos[stk[0]].first==pos[stk[1]].first){
					stk.push_back(stk.front());
					stk.pop_front();
				}
				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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 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 4992 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 7 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 4992 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 7 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 4992 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 7 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 4992 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 7 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -