Submission #311659

#	Time	Username	Problem	Language	Result	Execution time	Memory
311659		ant101	Building Skyscrapers (CEOI19_skyscrapers)	C++14	100 / 100	1811 ms	388276 KiB

skyscrapers

#include <bits/stdc++.h>
 
using namespace std;
 
using ii = pair<int, int>;
using ll = long long;
 
#define X first
#define Y second
 
int n, t, cnt;
unordered_map<ll, int> M;
ii cor[1500007];
int skynum[150007], sky[1500007];
int component[1500007];
bool engaged[1500007];
vector<int> incomp[1500007];
vector<int> G4[1500007], G8[1500007];
bool vis[1500007];
int ecnt;
int infty;
set<int, greater<int> > to_use;
bool hlp[1500007];
int turn, hlp2[1500007];
 
constexpr inline ll key(ii p) {
	return (ll)p.X * 1000696969LL + p.Y;
}
 
void add_point(int x, int y) {
	ii p = {x, y};
	if(!M.count(key(p))) {
		M[key(p)] = ++cnt;
		cor[cnt] = p;
		component[cnt] = cnt;
		incomp[cnt].push_back(cnt);
	}
}
 
bool check(int i) {
	bool eng[3][3];
	int comp[3][3];
	for(int w : G8[i]) {
		int x = cor[w].X - cor[i].X + 1;
		int y = cor[w].Y - cor[i].Y + 1;
		eng[x][y] = engaged[w];
		comp[x][y] = component[w];
	}
	
	if(!eng[0][1] && !eng[1][2] && comp[0][1] == comp[1][2] && eng[0][2]
		&& (eng[0][0] || eng[1][0] || eng[2][0] || eng[2][1] || eng[2][2]))
			return false;
	if(!eng[1][2] && !eng[2][1] && comp[1][2] == comp[2][1] && eng[2][2]
		&& (eng[2][0] || eng[1][0] || eng[0][0] || eng[0][1] || eng[0][2]))
			return false;
	if(!eng[2][1] && !eng[1][0] && comp[2][1] == comp[1][0] && eng[2][0]
		&& (eng[0][0] || eng[0][1] || eng[0][2] || eng[1][2] || eng[2][2]))
			return false;
	if(!eng[1][0] && !eng[0][1] && comp[1][0] == comp[0][1] && eng[0][0]
		&& (eng[0][2] || eng[1][2] || eng[2][2] || eng[2][1] || eng[2][0]))
			return false;
	if(!eng[0][1] && !eng[2][1] && comp[0][1] == comp[2][1]
		&& (eng[0][0] || eng[1][0] || eng[2][0]) && (eng[0][2] || eng[1][2] || eng[2][2]))
			return false;
	if(!eng[1][0] && !eng[1][2] && comp[1][0] == comp[1][2]
		&& (eng[0][0] || eng[0][1] || eng[0][2]) && (eng[2][0] || eng[2][1] || eng[2][2]))
			return false;
			
	if(comp[1][0] == component[infty] || comp[0][1] == component[infty]
		|| comp[2][1] == component[infty] || comp[1][2] == component[infty])	
			return true;
 
	return false;
}
 
void upd_check(int i) {
	bool c = check(skynum[i]);
	
	if(c && !hlp[i])
		to_use.insert(i);
	else if(!c && hlp[i])
		to_use.erase(i);
		
	hlp[i] = c;
}
 
void merge(int a, int b, bool upd = false) {
	if(a == b)
		return ;
		
	if(incomp[b].size() > incomp[a].size())
		swap(a, b);
		
	for(int x : incomp[b]) {
		incomp[a].push_back(x);
		component[x] = a;
	}
	
	if(upd) {
		turn++;
		for(int x : incomp[b]) {
			for(int y : G8[x]) {
				if(engaged[y] && hlp2[y] < turn) {
					upd_check(sky[y]);
					hlp2[y] = turn;
				}
			}
		}
	}
	
	incomp[b].clear();
}
 
void erase(int w) {
	engaged[w] = 0;
	for(int u : G4[w])
		if(!engaged[u])
			merge(component[w], component[u], true);
}
 
void dfs(int w) {
	if(vis[w])
		return ;
	vis[w] = 1;
	ecnt++;
		
	for(int u : G8[w])
		if(engaged[u])
			dfs(u);
}
 
int main() {	
	scanf("%d%d", &n, &t);
	
	M.reserve(262144);
	M.max_load_factor(0.25);
	
	ii minp = {1e9 + 7, 1e9 + 7};
	
	for(int i = 1 ; i <= n ; i++) {
		int r, c;
		scanf("%d%d", &r, &c);
		for(int x = -1 ; x <= 1 ; x++)
			for(int y = -1 ; y <= 1 ; y++)
				add_point(r + x, c + y);
		engaged[M[key({r, c})]] = 1;
		skynum[i] = M[key({r, c})];
		sky[M[key({r, c})]] = i;
		minp = min(minp, {r, c});
	}
	
	infty = M[key({minp.X - 1, minp.Y})];
	
	for(int i = 1 ; i <= cnt ; i++) {
		int x = cor[i].X;
		int y = cor[i].Y;
		
		for(int xo = -1 ; xo <= 1 ; xo++) {
			for(int yo = -1 ; yo <= 1 ; yo++) {
				ii p2 = {x + xo, y + yo};
				if(M.count(key(p2)) == 0)
					continue;
				int num = M[key(p2)];
				
				if(xo || yo)
					G8[i].push_back(num);
				if((xo || yo) && !(xo && yo)) {
					G4[i].push_back(num);
					if(!engaged[i] && !engaged[num])
						merge(component[i], component[num]);
				}
			}
		}
	}
	
	dfs(skynum[1]);
	if(ecnt != n) {
		printf("NO\n");
		return 0;
	}
	
	for(int i = 1 ; i <= n ; i++)
		upd_check(i);
	
	printf("YES\n");
	vector<int> res;
	for(int i = 0 ; i < n ; i++) {
		int s = *to_use.begin();
		to_use.erase(to_use.begin());
		res.push_back(s);
		erase(skynum[s]);
	}
	
	reverse(res.begin(), res.end());
	for(int x : res)
		printf("%d\n", x);
	
	return 0;
}

Compilation message (stderr)

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  133 |  scanf("%d%d", &n, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~
skyscrapers.cpp:142:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  142 |   scanf("%d%d", &r, &c);
      |   ~~~~~^~~~~~~~~~~~~~~~

• 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