Submission #198102

#	Time	Username	Problem	Language	Result	Execution time	Memory
198102		model_code	Building Skyscrapers (CEOI19_skyscrapers)	C++17	100 / 100	3054 ms	31808 KiB

skyscrapers

#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
#include<set>
using namespace std;

typedef pair<int, int> pii;
#define X first
#define Y second

const int dx[8] = {-1, 0, 1, 1, 1, 0, -1, -1}, dy[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
const int next_edge_dx[4][4] = {{0, 1, 0, -1}, {1, 1, -1, -1}, {1, 0, -1, 0}, {0, 0, 0, 0}};
const int next_edge_dy[4][4] = {{-1, 0, 1, 0}, {-1, 1, 1, -1}, {0, 1, 0, -1}, {0, 0, 0, 0}};
const int next_edge_dir[4][4] = {{2, 3, 0, 1}, {3, 0, 1, 2}, {0, 1, 2, 3}, {1, 2, 3, 0}};

uint64_t ptoh(pair<int, int> & p) {
    constexpr int C0 = 1000000000 + 10;
    uint64_t res = p.X+C0;
    res <<= 32;
    res += p.Y+C0;
    return res;
}

vector<pii> where_am_i;
map<uint64_t, int> who_is_here;
vector<bool> visited;

set<int> egligible;
vector<int> next_edge, prev_edge;
vector<int> edge_parent;
vector<int> edge_rank;
int outer_boss;

int get_boss(int eid) {
	if (edge_parent[eid] == -1) return eid;
	return edge_parent[eid] = get_boss(edge_parent[eid]);
}

void join_sets(int eid1, int eid2) {
	eid1 = get_boss(eid1);
	eid2 = get_boss(eid2);
	if (eid1 == eid2) return;
	if (edge_rank[eid1] < edge_rank[eid2]) swap(eid1, eid2);
	edge_parent[eid2] = eid1;
	if (outer_boss == eid2) outer_boss = eid1;
	edge_rank[eid1] = max(edge_rank[eid1], edge_rank[eid2] + 1);
}

int find_next_edge(int edge_id) {
	pii position = where_am_i[edge_id / 4];
	int direction = edge_id % 4;
	for (int i=0; i<4; i++) {
		pii nposition(position.X + next_edge_dx[i][direction], position.Y + next_edge_dy[i][direction]);
		auto it = who_is_here.find(ptoh(nposition));
		if (it != end(who_is_here)) {
			int next_tile_id = it->Y;
			return next_tile_id * 4 + next_edge_dir[i][direction];
		}
	}
}

void find_and_join_next(int edge_id) {
	int next_eid = find_next_edge(edge_id);
	next_edge[edge_id] = next_eid;
	prev_edge[next_eid] = edge_id;
	join_sets(edge_id, next_eid);
}

void join_edges(int tile_id) {
	pii position = where_am_i[tile_id];
	for (int direction = 0; direction < 4; direction++) {
		find_and_join_next(tile_id * 4 + direction);
	}
}


void check_egligible(int tile_id) {
	bool is_egligible = false;
	vector<int> distinct_loops;
	for (int direction=0; direction<4; direction++) {
		int eid = tile_id * 4 + direction;
		if (get_boss(eid) == outer_boss) is_egligible = true;
		int next_eid = find_next_edge(eid);
		if (next_eid / 4 != tile_id) {
			distinct_loops.push_back(get_boss(eid));
		}
	}
	
	for (int i=0; i<distinct_loops.size(); i++) {
		for (int j=0; j<i; j++) {
			if (distinct_loops[i] == distinct_loops[j]) is_egligible = false;
		}
	}
	
	if (is_egligible) {
		egligible.insert(tile_id);
	}
	else {
		if (egligible.count(tile_id) > 0) {
			egligible.erase(tile_id);
		}
	}
}

void get_possible_changes(int be_id, vector<int> &to_check) {
	to_check.push_back(be_id / 4);
	while (true) {
		int next_edge_id = find_next_edge(be_id);
		to_check.push_back(next_edge_id/4);
		if (get_boss(next_edge_id) == outer_boss) break;
		be_id = next_edge_id;
	}
}

void fix_edges_after_removal(int tile_id) {
	vector<int> to_check;
	for (int direction=0; direction<4; direction++) {
		int edge_id = tile_id * 4 + direction;
		int previous_edge_id = prev_edge[edge_id];
		if (previous_edge_id / 4 != tile_id) {
			if (get_boss(previous_edge_id) == outer_boss) {
				get_possible_changes(previous_edge_id, to_check);
			}
		}
	}
	for (int direction = 0; direction<4; direction++) {
		int edge_id = tile_id * 4 + direction;
		int previous_edge_id = prev_edge[edge_id];
		if (previous_edge_id / 4 != tile_id) {
			find_and_join_next(previous_edge_id);
		}
	}
	for (int tile_id : to_check) {
		check_egligible(tile_id);
	}
}

void dfs(int id) {
	if (visited[id]) return;
	visited[id] = true;
	for (int dir = 0; dir < 8; dir++) {
		pii ncoor(where_am_i[id].X + dx[dir], where_am_i[id].Y + dy[dir]);
		if (who_is_here.count(ptoh(ncoor)) > 0) {
			dfs(who_is_here[ptoh(ncoor)]);
		}
	}
}





int main() {
	int n, t;
	scanf("%d %d", &n, &t);
	where_am_i.resize(n);
	for (int i=0; i<n; i++) {
		scanf("%d %d", &where_am_i[i].X, &where_am_i[i].Y);
		who_is_here[ptoh(where_am_i[i])] = i;
	}
	
	visited.resize(n, false);
	dfs(0);
	for (bool v : visited) {
		if (!v) {
			printf("No\n");
			return 0;
		}
	}
	
	next_edge.resize(4*n);
	prev_edge.resize(4*n);
	edge_parent.resize(4*n, -1);
	edge_rank.resize(4*n, 0);
	
	outer_boss == -1;
	for (int i=0; i<n; i++) {
		join_edges(i);
	}
	
	int top_left = who_is_here.begin()->second;
	outer_boss = get_boss(top_left * 4 + 3);
	
	for (int i=0; i<n; i++) {
		check_egligible(i);
	}
	
	
	vector<int> result;
	while (!egligible.empty()) {
		
		/*fprintf(stderr, "egligible:");
		for (int x : egligible) {
			fprintf(stderr, " %d", x);
		}
		fprintf(stderr, "\n");*/
		
		auto it = egligible.end();
		it--;
		int current = *it;
		egligible.erase(current);
		who_is_here.erase(ptoh(where_am_i[current]));
		fix_edges_after_removal(current);
		
		result.push_back(current);
	}
	printf("Yes\n");
	reverse(result.begin(), result.end());
	for (int id : result) {
		printf("%d\n", id+1);
	}
	
	return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'void join_edges(int)':
skyscrapers.cpp:71:6: warning: variable 'position' set but not used [-Wunused-but-set-variable]
  pii position = where_am_i[tile_id];
      ^~~~~~~~
skyscrapers.cpp: In function 'void check_egligible(int)':
skyscrapers.cpp:90:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<distinct_loops.size(); i++) {
                ~^~~~~~~~~~~~~~~~~~~~~~
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:177:13: warning: statement has no effect [-Wunused-value]
  outer_boss == -1;
  ~~~~~~~~~~~^~~~~
skyscrapers.cpp: In function 'int find_next_edge(int)':
skyscrapers.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:156:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &t);
  ~~~~~^~~~~~~~~~~~~~~~~
skyscrapers.cpp:159:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &where_am_i[i].X, &where_am_i[i].Y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 12 / 12
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20
• Subtask 6: 10 / 10
• Subtask 7: 19 / 19