Submission #1004469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1004469		julian	Fliper (COCI22_fliper)	C++98	0 / 110	355 ms	84268 KiB

Main

#include <bits/stdc++.h>

struct Obstacle {
	size_t x, y;
	char c;
	size_t toL = std::numeric_limits<size_t>::max(), toR = std::numeric_limits<size_t>::max(), toT = std::numeric_limits<size_t>::max(), toB = std::numeric_limits<size_t>::max();
};

std::vector<long> uf_init(long n) {
	std::vector<long> uf(n);

	for (long i = 0; i < n; i++) {
		uf[i] = i;
	}

	return uf;
}

long uf_find(std::vector<long>& uf, long i) {
	if (uf[i] == i) return i;
	return uf[i] = uf_find(uf, uf[i]);
}

void uf_union(std::vector<long>& uf, long a, long b) {
	long aa = uf_find(uf, a);
	long bb = uf_find(uf, b);

	uf[aa] = bb;
}

void uf_converge(std::vector<long>& uf) {
	for (size_t i = 0; i < uf.size(); i++) {
		uf_find(uf, i);
	}
}

int main() {
	size_t n;
	std::cin >> n;

	std::vector<Obstacle> obstacles(n);

	for (size_t i = 0; i < n; i++) {
		size_t x, y;
		char c;
		std::cin >> x >> y >> c;

		obstacles[i] = {x, y, c};
	}

	std::vector<long> uf = uf_init(2 * n + 1);

	std::vector<size_t> xsort(n), ysort(n);
	for (size_t i = 0; i < n; i++) {
		xsort[i] = ysort[i] = i;
	}

	std::sort(xsort.begin(), xsort.end(), [&](size_t a, size_t b) {
		return obstacles[a].x < obstacles[b].x;
	});

	std::sort(ysort.begin(), ysort.end(), [&](size_t a, size_t b) {
		return obstacles[a].y < obstacles[b].y;
	});

	std::unordered_map<size_t, std::vector<size_t>> ymap, xmap;

	for (size_t i = 0; i < n; i++) {
		if (ymap.find(obstacles[xsort[i]].y) == ymap.end()) {
			ymap[obstacles[xsort[i]].y] = std::vector<size_t>(1, xsort[i]);
		} else {
			ymap[obstacles[xsort[i]].y].push_back(xsort[i]);
		}

		if (xmap.find(obstacles[ysort[i]].x) == xmap.end()) {
			xmap[obstacles[ysort[i]].x] = std::vector<size_t>(1, ysort[i]);
		} else {
			xmap[obstacles[ysort[i]].x].push_back(ysort[i]);
		}
	}

	for (auto& [y, obst] : ymap) {
		if (obstacles[obst[0]].c == '/') {
			uf_union(uf, obst[0] * 2, 2 * n);
		} else {
			uf_union(uf, obst[0] * 2 + 1, 2 * n);
		}

		if (obstacles[obst[obst.size() - 1]].c == '/') {
			uf_union(uf, obst[obst.size() - 1] * 2 + 1, 2 * n);
		} else {
			uf_union(uf, obst[obst.size() - 1] * 2, 2 * n);
		}

		for (size_t i = 0; i < obst.size() - 1; i++) {
			if (obstacles[obst[i]].c == '/') {
				if (obstacles[obst[i + 1]].c == '/') {
					uf_union(uf, obst[i] * 2 + 1, obst[i + 1] * 2);
				} else {
					uf_union(uf, obst[i] * 2 + 1, obst[i + 1] * 2 + 1);
				}
			} else {
				if (obstacles[obst[i + 1]].c == '/') {
					uf_union(uf, obst[i] * 2, obst[i + 1] * 2);
				} else {
					uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
				}
			}
		}
	}

	for (auto& [x, obst] : xmap) {
		if (obstacles[obst[0]].c == '/') {
			uf_union(uf, obst[0] * 2 + 1, 2 * n);
		} else {
			uf_union(uf, obst[0] * 2 + 1, 2 * n);
		}

		if (obstacles[obst[obst.size() - 1]].c == '/') {
			uf_union(uf, obst[obst.size() - 1] * 2, 2 * n);
		} else {
			uf_union(uf, obst[obst.size() - 1] * 2, 2 * n);
		}

		for (size_t i = 0; i < obst.size() - 1; i++) {
			if (obstacles[obst[i]].c == '/') {
				if (obstacles[obst[i + 1]].c == '/') {
					uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
				} else {
					uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
				}
			} else {
				if (obstacles[obst[i + 1]].c == '/') {
					uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
				} else {
					uf_union(uf, obst[i] * 2, obst[i + 1] * 2 + 1);
				}
			}
		}
	}

	uf_converge(uf);

	std::unordered_map<long, std::vector<std::pair<long, long>>> adj;

	for (size_t i = 0; i < uf.size() - 1; i += 2) {
		if (!(uf[i] == 2 * n && uf[i + 1] == 2 * n)) {
			adj[uf[i]].push_back({uf[i + 1], i / 2});
			adj[uf[i + 1]].push_back({uf[i], i / 2});
		}
	}

	for (auto [k, v] : adj) {
		if (k != 2 * n && v.size() % 8) {
			std::cout << -1 << std::endl;
			return 0;
		}
	}

	std::stack<long> s;

	s.push(2 * n);

	
	long color = 0;

	std::unordered_map<long, std::pair<std::vector<std::pair<long, long>>, std::vector<std::pair<long, long>>>> adj2;

	// First coloring
	while (!s.empty()) {
		long v = s.top();

		if (adj[v].empty()) {
			s.pop();
		} else {
			auto [u, obstI] = adj[v][adj[v].size() - 1];
			adj[v].erase(adj[v].end() - 1);
			adj[u].erase(std::find(adj[u].begin(), adj[u].end(), std::pair<long, long>(v, obstI)));
			s.push(u);

			if (color == 0) {
				adj2[v].first.push_back({u, obstI});
				adj2[u].first.push_back({v, obstI});
			} else {
				adj2[v].second.push_back({u, obstI});
				adj2[u].second.push_back({v, obstI});
			}

		
			color = (color + 1) % 2;

			//std::cout << v << " " << u << " " << obstI << std::endl;
		}
	}

	std::vector<long> colors(n, 9);
	color = 0;

	while (!s.empty()) s.pop();
	s.push(n * 2);
	// Second coloring (1)
	while (!s.empty()) {
		long v = s.top();

		if (adj2[v].first.empty()) {
			s.pop();
		} else {
			auto [u, obstI] = adj2[v].first[adj2[v].first.size() - 1];
			adj2[v].first.erase(adj2[v].first.end() - 1);
			adj2[u].first.erase(std::find(adj2[u].first.begin(), adj2[u].first.end(), std::pair<long, long>(v, obstI)));
			s.push(u);

			colors[obstI] = color + 1;
			color = (color + 1) % 2;

			//std::cout << v << " " << u << " " << obstI << std::endl;
		}
	}

	color = 0;

	while (!s.empty()) s.pop();
	s.push(n * 2);

	// Second coloring (2)
	while (!s.empty()) {
		long v = s.top();

		if (adj2[v].second.empty()) {
			s.pop();
		} else {
			auto [u, obstI] = adj2[v].second[adj2[v].second.size() - 1];
			adj2[v].second.erase(adj2[v].second.end() - 1);
			adj2[u].second.erase(std::find(adj2[u].second.begin(), adj2[u].second.end(), std::pair<long, long>(v, obstI)));
			s.push(u);

			colors[obstI] = color + 3;
			color = (color + 1) % 2;

			//std::cout << v << " " << u << " " << obstI << std::endl;
		}
	}

	color = 0;

	for (auto& c : colors) {
		if (c == 9) {
			c = color + 1;
			color = (color + 1) % 4;
		}
	}


	//std::cout << "COLORS" << std::endl;

	for (auto c : colors) {
		std::cout << c << " ";
	}
	std::cout << std::endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:82:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   82 |  for (auto& [y, obst] : ymap) {
      |             ^
Main.cpp:112:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  112 |  for (auto& [x, obst] : xmap) {
      |             ^
Main.cpp:147:15: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  147 |   if (!(uf[i] == 2 * n && uf[i + 1] == 2 * n)) {
Main.cpp:147:37: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type' {aka 'long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  147 |   if (!(uf[i] == 2 * n && uf[i + 1] == 2 * n)) {
Main.cpp:153:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  153 |  for (auto [k, v] : adj) {
      |            ^
Main.cpp:154:9: warning: comparison of integer expressions of different signedness: 'std::tuple_element<0, std::pair<const long int, std::vector<std::pair<long int, long int> > > >::type' {aka 'const long int'} and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  154 |   if (k != 2 * n && v.size() % 8) {
      |       ~~^~~~~~~~
Main.cpp:176:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  176 |    auto [u, obstI] = adj[v][adj[v].size() - 1];
      |         ^
Main.cpp:208:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |    auto [u, obstI] = adj2[v].first[adj2[v].first.size() - 1];
      |         ^
Main.cpp:232:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  232 |    auto [u, obstI] = adj2[v].second[adj2[v].second.size() - 1];
      |         ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 70