답안 #439373

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
439373 2021-06-29T17:34:20 Z algorithm16 분수 공원 (IOI21_parks) C++17
컴파일 오류
0 ms 0 KB
//#include "parks.h"
#include<iostream>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
vector <int> v[200005],vx,vy,u2,c2,v2,a2,b2;
vector <pair<pair<int,int>,int> > v1;
set <pair<int,int> > s;
vector <pair<int,int> > c;
bool comp(pair<pair<int,int>,int> a,pair<pair<int,int>,int> b) {
	return a.first.second<b.first.second;
}
int bio[200005],dx[4]={1,1,-1,-1},dy[4]={1,-1,1,-1},cnt;
void dfs(int x) {
	bio[x]=1;
	cnt+=1;
	c2.push_back(x);
	for(int i=0;i<v[x].size();i++) {
		if(!bio[v[x][i]]) {
			c.push_back(make_pair(x,v[x][i]));
			dfs(v[x][i]);
		}
	}
}
int ok(int x,int y,int a,int b) {
	if(vx[a]==vx[b] && abs(x-vx[a])==1 && y==(vy[a]+vy[b])/2) return 1;
	if(vy[a]==vy[b] && abs(y-vy[a])==1 && x==(vx[a]+vx[b])/2) return 1;
	return 0;
}
int construct_roads(std::vector<int> x,std::vector<int> y) {
	vx=x;
	vy=y;
	int n=x.size(),minx=1e9,maxx=-1e9;
    if(n==1) {
		build({},{},{},{});
        return 1;
    }
    for(int i=0;i<n;i++) {
    	v1.push_back(make_pair(make_pair(x[i],y[i]),i));
    	s.insert(make_pair(x[i]-1,y[i]-1));
    	s.insert(make_pair(x[i]+1,y[i]-1));
    	s.insert(make_pair(x[i]-1,y[i]+1));
    	s.insert(make_pair(x[i]+1,y[i]+1));
    	maxx=max(maxx,x[i]);
    	minx=min(minx,x[i]);
	}
	sort(v1.begin(),v1.end(),comp);
	for(int i=0;i<v1.size();i++) {
		for(int j=i+1;j<v1.size() && j-i<=5;j++) {
			int x1=v1[i].first.first,y1=v1[i].first.second,x2=v1[j].first.first,y2=v1[j].first.second,i2=v1[i].second,j2=v1[j].second;
			if((abs(x1-x2)==2 && y1==y2) || (abs(y1-y2)==2 && x1==x2)) {
				v[i2].push_back(j2);
				v[j2].push_back(i2);
				u2.push_back(i2);
				v2.push_back(j2);
				//cout << i2 << " " << j2 << "\n";
			}
		}
	}
	dfs(0);
    //cout << cnt << "\n";
    if(cnt<n) return 0;
    if(minx>=2 && maxx<=4) {
    	for(int i=0;i<u2.size();i++) {
	    	if(y[u2[i]]==y[v2[i]]) {
	    		a2.push_back(3);
	    		b2.push_back(y[v2[i]]-1);
			}
			else if(x[u2[i]]==4) {
				a2.push_back(5);
				b2.push_back(y[v2[i]]-1);
			}
			else {
				a2.push_back(1);
				b2.push_back(y[v2[i]]-1);
			}
		}
	}
	else {
		u2.clear();
		v2.clear();
		for(int i=0;i<n-1;i++) {
			a2.push_back(-1);
			b2.push_back(-1);
			u2.push_back(c[i].first);
			v2.push_back(c[i].second);
		}
		for(int i=0;i<n-1;i++) {
			for(int j=0;j<4;j++) {
				if(s.find(make_pair(x[c2[i]]+dx[j],y[c2[i]]+dy[j]))!=s.end() && ok(x[c2[i]]+dx[j],y[c2[i]]+dy[j],u2[i],v2[i])) {
					a2[i]=x[c2[i]]+dx[j];
					b2[i]=y[c2[i]]+dy[j];
					s.erase(make_pair(x[c2[i]]+dx[j],y[c2[i]]+dy[j]));
					break;
				}
				if(s.find(make_pair(x[c2[i+1]]+dx[j],y[c2[i+1]]+dy[j]))!=s.end() && ok(x[c2[i+1]]+dx[j],y[c2[i+1]]+dy[j],u2[i],v2[i])) {
					a2[i]=x[c2[i+1]]+dx[j];
					b2[i]=y[c2[i+1]]+dy[j];
					s.erase(make_pair(x[c2[i+1]]+dx[j],y[c2[i+1]]+dy[j]));
					break;
				}
			}
		}
		/*cout << "\n\n";
		for(int i=0;i<u2.size();i++) {
			cout << u2[i] << " " << v2[i] << "\n";
		}
		cout << "\n";
		for(int i=0;i<a2.size();i++) {
			cout << a2[i] << " " << b2[i] << "\n";
		}*/
	}
    build(u2,v2,a2,b2);
    return 1;
}

Compilation message

parks.cpp: In function 'void dfs(int)':
parks.cpp:19:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0;i<v[x].size();i++) {
      |              ~^~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:36:3: error: 'build' was not declared in this scope
   36 |   build({},{},{},{});
      |   ^~~~~
parks.cpp:49:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |  for(int i=0;i<v1.size();i++) {
      |              ~^~~~~~~~~~
parks.cpp:50:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int j=i+1;j<v1.size() && j-i<=5;j++) {
      |                 ~^~~~~~~~~~
parks.cpp:65:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      for(int i=0;i<u2.size();i++) {
      |                  ~^~~~~~~~~~
parks.cpp:114:5: error: 'build' was not declared in this scope
  114 |     build(u2,v2,a2,b2);
      |     ^~~~~