Submission #481504

#	Time	Username	Problem	Language	Result	Execution time	Memory
481504		8e7	분수 공원 (IOI21_parks)	C++17	0 / 100	1 ms	204 KiB

parks

//Challenge: Accepted
#include "parks.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct pnt{
	int x, y, id;
	pnt(){x = y = id = 0;}
	pnt(int a, int b, int c){x = a, y = b, id = c;}
};
int par[maxn];
int find(int a) {
	return a == par[a] ? a : par[a] = find(par[a]);
}
int num = 0;
bool Union (int a, int b) {
	//debug(a, b);
	a = find(a), b = find(b);
	if (a == b) return false;
	//debug(1);
	num--;
	par[find(a)] = find(b);
	return true;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
	int n = x.size();
	for (int i = 0;i < n;i++) par[i] = i;
	num = n;
	vector<pnt> a, b;
	for (int i = 0;i < n;i++) {
		if (x[i] == 2)a.push_back(pnt(y[i], x[i], i));
		else b.push_back(pnt(y[i], x[i], i));
	}
    if (x.size() == 1) {
		build({}, {}, {}, {});
        return 1;
    }
	sort(a.begin(), a.end(), [&](pnt p, pnt q){return (p.x == q.x ? p.y < q.y : p.x < q.x);});
	sort(b.begin(), b.end(), [&](pnt p, pnt q){return (p.x == q.x ? p.y < q.y : p.x < q.x);});
    vector<int> u, v, ax, ay;
	int id = 0;
	for (int i = 0;i < a.size();i++) {
		while (id < b.size() && b[id].x < a[i].x) id++;
		if (i && a[i].x - a[i-1].x == 2) {
			if (Union(a[i].id, a[i-1].id)) {
				u.push_back(a[i].id), v.push_back(a[i-1].id);
				ax.push_back(a[i].x - 1), ay.push_back(a[i].y - 1);
			}	
		}
		if (id < b.size() && a[i].x == b[id].x) {
			if (Union(a[i].id, b[id].id)) {
				u.push_back(a[i].id), v.push_back(b[id].id);
				ax.push_back(a[i].x - 1), ay.push_back(a[i].y + 1);
			}
		}
	}	
	for (int i = 1;i < b.size();i++) {
		if (b[i].x - b[i-1].x == 2) {
			if (Union(b[i].id, b[i-1].id)) {
				u.push_back(b[i].id), v.push_back(b[i-1].id);
				ax.push_back(b[i].x - 1), ay.push_back(b[i].y + 1);
			}
		}
	}
	if (num > 1) return 0;
	build(u, v, ax, ay);
    return 1;
}
/*
5
2 2
4 2
4 4
4 6
2 6
*/

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:58:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for (int i = 0;i < a.size();i++) {
      |                 ~~^~~~~~~~~~
parks.cpp:59:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   while (id < b.size() && b[id].x < a[i].x) id++;
      |          ~~~^~~~~~~~~~
parks.cpp:66:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   if (id < b.size() && a[i].x == b[id].x) {
      |       ~~~^~~~~~~~~~
parks.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pnt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 1;i < b.size();i++) {
      |                 ~~^~~~~~~~~~

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