Submission #223385

#	Time	Username	Problem	Language	Result	Execution time	Memory
223385		jamielim	Matching (COCI20_matching)	C++14	18 / 110	30 ms	25472 KiB

matching

#include <bits/stdc++.h>
using namespace std;

int n;
pair<int,int> arr[100005];
pair<int,int> adj[2][100005];
vector<int> al[100005];

struct node{
	int s,e,m,v;
	node *l,*r;
	node(int S,int E){
		s=S;e=E;m=(s+e)/2;v=0;
		if(s!=e){l=new node(s,m);r=new node(m+1,e);}
	}
	void upd(int x,int add){
		if(s==e){v+=add;return;}
		if(x<=m)l->upd(x,add);
		else r->upd(x,add);
		v=l->v+r->v;
	}
	int qry(int x,int y){
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return l->qry(x,m)+r->qry(m+1,y);
	}
}*root; //point modify range sum query

bool poss(vector<pair<int,int> > v){
	//check whether the connections here intersect (false) or not (true)
	vector<pair<int,int> > hor,ver[100005];
	for(int i=0;i<(int)v.size();i++){
		if(arr[v[i].first].first==arr[v[i].second].first){
			ver[arr[v[i].first].first].push_back(make_pair(arr[v[i].first].second,arr[v[i].second].second));
		}else{
			int a=arr[v[i].first].first,b=arr[v[i].second].first;
			if(a>b)swap(a,b);
			hor.push_back(make_pair(a,arr[v[i].first].second));hor.push_back(make_pair(b,-arr[v[i].second].second));
		}
	}
	sort(hor.begin(),hor.end());
	root=new node(0,100005);
	int ptr=0;
	for(int i=0;i<100005;i++){
		while(ptr<(int)hor.size()&&hor[ptr].first<=i){
			if(hor[ptr].second>0)root->upd(hor[ptr].second,1);
			else root->upd(-hor[ptr].second,-1);
			ptr++;
		}
		for(int j=0;j<(int)ver[i].size();j++){
			int a=ver[i][j].first,b=ver[i][j].second;
			if(a>b)swap(a,b);
			if(root->qry(a,b)>0){
				return false;
			}
		}
	}
	return true;
}

int main(){
	scanf("%d",&n);
	for(int i=0;i<100005;i++)adj[0][i]=adj[1][i]=make_pair(-1,-1);
	for(int i=0;i<n;i++){
		scanf("%d%d",&arr[i].first,&arr[i].second);
		if(adj[0][arr[i].first].first==-1)adj[0][arr[i].first].first=i;
		else adj[0][arr[i].first].second=i;
		if(adj[1][arr[i].second].first==-1)adj[1][arr[i].second].first=i;
		else adj[1][arr[i].second].second=i;
	}
	for(int i=0;i<n;i++){
		if(adj[0][arr[i].first].second==-1&&adj[1][arr[i].second].second==-1){ //no friends
			printf("NE");return 0;
		}
		if(adj[0][arr[i].first].second!=-1){ //vertical friend
			if(adj[0][arr[i].first].first==i)al[i].push_back(adj[0][arr[i].first].second);
			else al[i].push_back(adj[0][arr[i].first].first);
		}
		if(adj[1][arr[i].second].second!=-1){ //horizontal friend
			if(adj[1][arr[i].second].first==i)al[i].push_back(adj[1][arr[i].second].second);
			else al[i].push_back(adj[1][arr[i].second].first);
		}
		//draw directed edges, the other direction will be drawn by the other person
	}
	//for(int i=0;i<n;i++){for(int j=0;j<(int)al[i].size();j++)printf("%d ",al[i][j]);printf("\n");}
	vector<pair<int,int> > ans;
	//consider "forced" friends (degree 1)
	queue<int> q;
	for(int i=0;i<n;i++){
		if((int)al[i].size()==1)q.push(i);
	}
	while(!q.empty()){
		int cur=q.front();q.pop();
		for(int i=0;i<(int)al[cur].size();i++){ //1 or 0
			int x=al[cur][i];
			if((int)al[x].size()==2){
				if(al[x][0]==cur){
					al[x][0]=al[x][1];
				}
				al[x].pop_back(); //get rid of cur from x friend list
				ans.push_back(make_pair(cur,x));
				//now x not allowed to have friends anymore
				int y=al[x][0];
				if((int)al[y].size()==1){
					printf("NE"); return 0;
					//y has no friends because x is friends with cur
				}else{
					assert((int)al[y].size()==2);
					if(al[y][0]==x)al[y][0]=al[y][1];
					al[y].pop_back();
					q.push(y); //push cur's friend's friend into the queue
				}
			}else if((int)al[x].size()==1){
				ans.push_back(make_pair(cur,x));
			}
			al[x].clear();
		}
		al[cur].clear();
	}
	//for(int i=0;i<n;i++){for(int j=0;j<(int)al[i].size();j++)printf("%d ",al[i][j]);printf("\n");}
	//everything left in al is degree 2, connect these in one direction
	vector<pair<int,int> > ans2;for(int i=0;i<(int)ans.size();i++)ans2.push_back(ans[i]);
	//ans is vertical, ans2 is horizontal. need to check whether things intersect at the end
	for(int i=0;i<n;i++){
		if((int)al[i].size()==0)continue;
		assert((int)al[i].size()==2);
		if(arr[al[i][0]].first==arr[i].first&&al[i][0]<i){
			ans.push_back(make_pair(al[i][0],i));
		}else if(arr[al[i][1]].first==arr[i].first&&al[i][1]<i){
			ans.push_back(make_pair(al[i][1],i));
		}
		if(arr[al[i][0]].second==arr[i].second&&al[i][0]<i){
			ans2.push_back(make_pair(al[i][0],i));
		}else if(arr[al[i][1]].second==arr[i].second&&al[i][1]<i){
			ans2.push_back(make_pair(al[i][1],i));
		}
	}
	if(poss(ans)){
		if(n>40)return 1;
		printf("DA\n");
		for(int i=0;i<(int)ans.size();i++){
			printf("%d %d\n",ans[i].first+1,ans[i].second+1);
		}
	}else if(poss(ans2)){
		if(n>40)return 2;
		printf("DA\n");
		for(int i=0;i<(int)ans2.size();i++){
			printf("%d %d\n",ans2[i].first+1,ans2[i].second+1);
		}
	}else{
		printf("NE");
	}
}

Compilation message (stderr)

matching.cpp: In function 'int main()':
matching.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
matching.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&arr[i].first,&arr[i].second);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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