제출 #435500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
435500		kshitij_sodani	분수 공원 (IOI21_parks)	C++17	70 / 100	2227 ms	168692 KiB

parks

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;

#include "parks.h"
int par[300001];
int ss[300001];
int find(int no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
map<pair<int,int>,int> mid;
map<int,pair<int,int>> mid2;
int ind5=-1;
void add(int i,int j){
	if(mid.find({i,j})==mid.end()){
		//ind5++;
		mid[{i,j}]=ind5;
		mid2[ind5]={i,j};
		ind5++;
	}
}
vector<int> adj2[2000001];
int dd[2000001];
int vis[2000001];
//vector<int> adj3[300001];
int construct_roads(vector<int> x, std::vector<int> y) {
    int n=x.size();

   // sort(y,y+n);
   	vector<int> uu, vv, aa, bb;
   	vector<pair<int,int>> zz;
   	map<pair<int,int>,int> xx;
   	for(int i=0;i<n;i++){
   		xx[{x[i],y[i]}]=i;
   		par[i]=i;
   	}
   	map<pair<int,int>,int> kk;
   	for(int i=0;i<n;i++){
   		if(xx.find({x[i],y[i]+2})!=xx.end()){
   			int x1=find(i);
   			int y1=find(xx[{x[i],y[i]+2}]);
   			if(x1!=y1){
   				par[x1]=y1;
   				uu.pb(i);
   				vv.pb(xx[{x[i],y[i]+2}]);
   				
   			}
   		}
   	}
   	for(int i=0;i<n;i++){
   		if(xx.find({x[i]+2,y[i]})!=xx.end()){
   			int x1=find(i);
   			int y1=find(xx[{x[i]+2,y[i]}]);
   			if(x1!=y1){
   				par[x1]=y1;
   				uu.pb(i);
   				vv.pb(xx[{x[i]+2,y[i]}]);
   			}
   		}
   	}


   	for(int i=0;i<n;i++){
   		par[i]=find(i);
   	}

   	for(int i=0;i<n;i++){
   		if(par[i]!=par[0]){
   			return 0;
   		}
   	}
   	ind5=uu.size();
   	for(int i=0;i<uu.size();i++){
   		aa.pb(-1);
   		bb.pb(-1);
   		if(x[uu[i]]+2==x[vv[i]]){
   			//
   			add(x[uu[i]]+1,y[uu[i]]+1);
   			add(x[uu[i]]+1,y[uu[i]]-1);
   			adj2[i].pb(mid[{x[uu[i]]+1,y[uu[i]]+1}]);
   			//adj2[mid[{x[uu[i]]+1,y[uu[i]]+1}]].pb(i);
   			adj2[i].pb(mid[{x[uu[i]]+1,y[uu[i]]-1}]);
   			//adj2[mid[{x[uu[i]]+1,y[uu[i]]-1}]].pb(i);
   		}
   		else{
   			add(x[uu[i]]+1,y[uu[i]]+1);
   			add(x[uu[i]]-1,y[uu[i]]+1);
   			adj2[i].pb(mid[{x[uu[i]]+1,y[uu[i]]+1}]);
   			adj2[i].pb(mid[{x[uu[i]]-1,y[uu[i]]+1}]);
   		}
   	}
   	for(int i=0;i<uu.size();i++){
   		for(auto j:adj2[i]){
   			adj2[j].pb(i);
   		}
   	}
   	set<pair<int,int>> ee;
   	for(int i=0;i<ind5;i++){
   		if(adj2[i].size()==0){
   			return 0;
   		}
   		dd[i]=adj2[i].size();
   		ee.insert({adj2[i].size(),i});
   	}
   	while(ee.size()){
   		pair<int,int> no=*ee.begin();
   		if(no.a==0){
   			if(no.b<uu.size()){
   				return 0;
   			}
   			ee.erase(no);
   			vis[no.b]=1;
   			continue;
   		}
   		int st=-1;
   		for(auto j:adj2[no.b]){
   			if(vis[j]==0){
   				st=j;
   			}
   		}
   		vis[st]=1;
   		vis[no.b]=1;
   		ee.erase({dd[no.b],no.b});
   		ee.erase({dd[st],st});
   		int ac=no.b;
   		int bc=st;
   		if(ac>bc){
   			swap(ac,bc);
   		}
   		aa[ac]=mid2[bc].a;
   		bb[ac]=mid2[bc].b;
   		for(auto j:adj2[no.b]){
   			if(vis[j]==0){
   				ee.erase({dd[j],j});
   				dd[j]--;

   				ee.insert({dd[j],j});
   			}
   		}
   		for(auto j:adj2[st]){
   			if(vis[j]==0){
   				ee.erase({dd[j],j});
   				dd[j]--;

   				ee.insert({dd[j],j});
   			}
   		}
   	}

  /* 	for(int i=0;i<n;i++){
   		zz.pb({y[i],i});
   	}
   	sort(zz.begin(),zz.end());
   	for(int i=0;i<n-1;i++){
   		if(zz[i+1].a-zz[i].a>2){
   			return 0;
   		}
   		uu.pb(zz[i].b);
   		vv.pb(zz[i+1].b);
   		aa.pb(1);
   		bb.pb(zz[i].a+1);
   	}*/
   	build(uu,vv,aa,bb);

   	return 1;
    /*if (x.size() == 1)
        return 0;
    
    u.push_back(0);
    v.push_back(1);
    a.push_back(x[0]+1);
    b.push_back(y[0]-1);
    build(u, v, a, b);
    return 1;*/
}

컴파일 시 표준 에러 (stderr) 메시지

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:80:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i=0;i<uu.size();i++){
      |                 ~^~~~~~~~~~
parks.cpp:99:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |     for(int i=0;i<uu.size();i++){
      |                 ~^~~~~~~~~~
parks.cpp:115:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |       if(no.b<uu.size()){
      |          ~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30