답안 #831687

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
831687 2023-08-20T12:21:02 Z andrey27_sm 분수 공원 (IOI21_parks) C++17
컴파일 오류
0 ms 0 KB
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> cons[200001];
int mask_l[200001];
vector<int> u;
vector<int> v;
vector<int> a;
vector<int> b;
struct dsu{
	int sz = 0;
	vector<int> pr;
	int p(int v){
		if(pr[v] == v) return v;
		return pr[v] = p(pr[v]);
	}
	bool un(int u,int v){
		u = p(u);
		v = p(v);
		if(u == v) return 0 ;
		pr[u] = v;
		sz++;
		return 1;
	}
} D;
struct edge{
	int x;
	int y;
	int type; // 0 - vert, 1 - hor;
	int a;
	int b;
};
int construct_roads(vector<int> x, vector<int> y) {
	int n = x.size();
	D.pr.resize(n);
	for (int i = 0; i < n; ++i)
	{
		D.pr[i] = i;
	}
	vector<edge> E;
	vector<pair<int,pair<int,int>>> x_d;
	vector<pair<int,pair<int,int>>> y_d;
	for (int i = 0; i < n; ++i)
	{
		x_d.push_back({x[i],{y[i],i}});
		y_d.push_back({y[i],{x[i],i}});
	} 
	sort(x_d.begin(), x_d.end());
	sort(y_d.begin(), y_d.end());
	for (int i = 1; i < n; ++i)
	{
		if(x_d[i].first == x_d[i-1].first and x_d[i].second.first-2 == x_d[i-1].second.first){
			D.un(x_d[i-1].second.second,x_d[i].second.second);
			E.push_back({x_d[i-1].first,x_d[i-1].second.first,0,x_d[i-1].second.second,x_d[i].second.second});
		}
	}
	for (int i = 1; i < n; ++i)
	{
		if(y_d[i].first == y_d[i-1].first and y_d[i].second.first-2 == y_d[i-1].second.first){
			D.un(y_d[i-1].second.second,y_d[i].second.second);
			E.push_back({y_d[i-1].second.first,y_d[i-1].first,1,y_d[i-1].second.second,y_d[i].second.second});
			
		}
	}
	if(D.sz != n-1) return 0;
	set<pair<int,int>> lines;
	set<pair<int,int>> points;
	sort(E.begin(),E.end(),[](auto a,auto b){
		if(a.x != b.x) return a.x < b.x;
		if(a.type != b.type) return a.type < b.type;
		return a.y < b.y;
	});
	for (int i = 0; i < E.size(); ++i)
	{
		if(E[i].type == 0) lines.insert({E[i].x,E[i].y});
	}
	//assert(E.size() <= n-1);
	for (int i = 0; i < E.size(); ++i)
	{
		//cout << E[i].x << " " << E[i].y << "   --\n";
		if(E[i].type == 0){
			if(points.count({E[i].x-1,E[i].y+1}) == 0){
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x-1);
				b.push_back(E[i].y+1);
				points.insert({E[i].x-1,E[i].y+1});
			}
			else if(points.count({E[i].x+1,E[i].y+1}) == 0){				
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x+1);
				b.push_back(E[i].y+1);
				points.insert({E[i].x+1,E[i].y+1});
			}
			else return 0;
		}
		else{
			int top = 0;
			if(points.count({E[i].x+1,E[i].y-1})) top = 1;
			else if(points.count({E[i].x+1,E[i].y+1})) top = 2;
			if(top == 0 and lines.count({E[i].x+2,E[i].y-2})) top = 1;
			if(top == 0 and lines.count({E[i].x+2,E[i].y}))) top = 2;
			if(top%2 == 0){
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x+1);
				b.push_back(E[i].y-1);
				points.insert({E[i].x+1,E[i].y-1});
			}
			else{				
				u.push_back(E[i].a);
				v.push_back(E[i].b);
				a.push_back(E[i].x+1);
				b.push_back(E[i].y+1);
				points.insert({E[i].x+1,E[i].y+1});
			}
		}
	}
	//if(points.size() != n-1) return 0;
	build(u,v,a,b);
	return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < E.size(); ++i)
      |                  ~~^~~~~~~~~~
parks.cpp:78:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for (int i = 0; i < E.size(); ++i)
      |                  ~~^~~~~~~~~~
parks.cpp:103:51: error: expected primary-expression before ')' token
  103 |    if(top == 0 and lines.count({E[i].x+2,E[i].y}))) top = 2;
      |                                                   ^