oj.uz

Submission #248386

# Submission time Handle Problem Language Result Execution time Memory
248386 2020-07-12T10:37:56 Z mieszko11b Building Skyscrapers (CEOI19_skyscrapers) C++14
51 / 100
 3500 ms 156424 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int n, t, cnt;
map<ii, int> M;
ii cor[1000007];
int skynum[150007];
int component[1000007];
bool engaged[1000007];
vector<int> incomp[1000007];
vector<int> G4[1000007], G8[1000007];
bool vis[1000007];
int ecnt;
int infty;

void add_point(int x, int y) {
	ii p = {x, y};
	if(!M.count(p)) {
		M[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 merge(int a, int b) {
	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;
	}
	incomp[b].clear();
}

void erase(int w) {
	engaged[w] = 0;
	for(int u : G4[w])
		if(!engaged[u])
			merge(component[w], component[u]);
}

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);
	
	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[{r, c}]] = 1;
		skynum[i] = M[{r, c}];
		minp = min(minp, {r, c});
	}
	
	infty = M[{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(p2) == 0)
					continue;
				int num = M[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;
	}
	
	printf("YES\n");
	vector<int> res;
	for(int i = 0 ; i < n ; i++) {
		for(int j = n ; j >= 1 ; j--) {
			if(engaged[skynum[j]] && check(skynum[j])) {
				erase(skynum[j]);
				res.push_back(j);
				break;
			}
		}
	}
	
	reverse(res.begin(), res.end());
	for(int x : res)
		printf("%d\n", x);
	
	return 0;
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:101: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:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &r, &c);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB ans=YES N=1
2 Correct 36 ms 70784 KB ans=YES N=4
3 Correct 37 ms 70780 KB ans=NO N=4
4 Correct 37 ms 70784 KB ans=YES N=5
5 Correct 37 ms 70776 KB ans=YES N=9
6 Correct 35 ms 70784 KB ans=YES N=5
7 Correct 37 ms 70780 KB ans=NO N=9
8 Correct 38 ms 70788 KB ans=NO N=10
9 Correct 37 ms 70776 KB ans=YES N=10
10 Correct 47 ms 70776 KB ans=YES N=10
11 Correct 38 ms 70776 KB ans=YES N=10
12 Correct 36 ms 70784 KB ans=YES N=9
13 Correct 36 ms 70784 KB ans=YES N=9
14 Correct 36 ms 70776 KB ans=YES N=8
15 Correct 37 ms 70776 KB ans=YES N=8
16 Correct 37 ms 70780 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB ans=YES N=1
2 Correct 36 ms 70784 KB ans=YES N=4
3 Correct 37 ms 70780 KB ans=NO N=4
4 Correct 37 ms 70784 KB ans=YES N=5
5 Correct 37 ms 70776 KB ans=YES N=9
6 Correct 35 ms 70784 KB ans=YES N=5
7 Correct 37 ms 70780 KB ans=NO N=9
8 Correct 38 ms 70788 KB ans=NO N=10
9 Correct 37 ms 70776 KB ans=YES N=10
10 Correct 47 ms 70776 KB ans=YES N=10
11 Correct 38 ms 70776 KB ans=YES N=10
12 Correct 36 ms 70784 KB ans=YES N=9
13 Correct 36 ms 70784 KB ans=YES N=9
14 Correct 36 ms 70776 KB ans=YES N=8
15 Correct 37 ms 70776 KB ans=YES N=8
16 Correct 37 ms 70780 KB ans=NO N=2
17 Correct 36 ms 70776 KB ans=YES N=17
18 Correct 35 ms 70776 KB ans=YES N=25
19 Correct 37 ms 70776 KB ans=YES N=100
20 Correct 42 ms 70904 KB ans=YES N=185
21 Correct 39 ms 71032 KB ans=NO N=174
22 Correct 36 ms 70776 KB ans=YES N=90
23 Correct 36 ms 70776 KB ans=YES N=63
24 Correct 37 ms 70776 KB ans=YES N=87
25 Correct 37 ms 70784 KB ans=YES N=183
26 Correct 40 ms 70912 KB ans=YES N=188
27 Correct 51 ms 70904 KB ans=YES N=183
28 Correct 43 ms 70904 KB ans=YES N=189
29 Correct 37 ms 70904 KB ans=YES N=200
30 Correct 54 ms 70904 KB ans=YES N=190
31 Correct 38 ms 70912 KB ans=YES N=187
32 Correct 46 ms 70904 KB ans=YES N=187
33 Correct 37 ms 70912 KB ans=YES N=182
34 Correct 38 ms 70904 KB ans=YES N=184
35 Correct 39 ms 70904 KB ans=YES N=188
36 Correct 38 ms 70904 KB ans=YES N=181
37 Correct 39 ms 70904 KB ans=YES N=188
38 Correct 40 ms 70912 KB ans=YES N=191
39 Correct 37 ms 70904 KB ans=YES N=196
40 Correct 38 ms 70904 KB ans=YES N=196
41 Correct 37 ms 70904 KB ans=YES N=196
42 Correct 38 ms 70904 KB ans=YES N=196
43 Correct 38 ms 70904 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB ans=YES N=1
2 Correct 36 ms 70784 KB ans=YES N=4
3 Correct 37 ms 70780 KB ans=NO N=4
4 Correct 37 ms 70784 KB ans=YES N=5
5 Correct 37 ms 70776 KB ans=YES N=9
6 Correct 35 ms 70784 KB ans=YES N=5
7 Correct 37 ms 70780 KB ans=NO N=9
8 Correct 38 ms 70788 KB ans=NO N=10
9 Correct 37 ms 70776 KB ans=YES N=10
10 Correct 47 ms 70776 KB ans=YES N=10
11 Correct 38 ms 70776 KB ans=YES N=10
12 Correct 36 ms 70784 KB ans=YES N=9
13 Correct 36 ms 70784 KB ans=YES N=9
14 Correct 36 ms 70776 KB ans=YES N=8
15 Correct 37 ms 70776 KB ans=YES N=8
16 Correct 37 ms 70780 KB ans=NO N=2
17 Correct 36 ms 70776 KB ans=YES N=17
18 Correct 35 ms 70776 KB ans=YES N=25
19 Correct 37 ms 70776 KB ans=YES N=100
20 Correct 42 ms 70904 KB ans=YES N=185
21 Correct 39 ms 71032 KB ans=NO N=174
22 Correct 36 ms 70776 KB ans=YES N=90
23 Correct 36 ms 70776 KB ans=YES N=63
24 Correct 37 ms 70776 KB ans=YES N=87
25 Correct 37 ms 70784 KB ans=YES N=183
26 Correct 40 ms 70912 KB ans=YES N=188
27 Correct 51 ms 70904 KB ans=YES N=183
28 Correct 43 ms 70904 KB ans=YES N=189
29 Correct 37 ms 70904 KB ans=YES N=200
30 Correct 54 ms 70904 KB ans=YES N=190
31 Correct 38 ms 70912 KB ans=YES N=187
32 Correct 46 ms 70904 KB ans=YES N=187
33 Correct 37 ms 70912 KB ans=YES N=182
34 Correct 38 ms 70904 KB ans=YES N=184
35 Correct 39 ms 70904 KB ans=YES N=188
36 Correct 38 ms 70904 KB ans=YES N=181
37 Correct 39 ms 70904 KB ans=YES N=188
38 Correct 40 ms 70912 KB ans=YES N=191
39 Correct 37 ms 70904 KB ans=YES N=196
40 Correct 38 ms 70904 KB ans=YES N=196
41 Correct 37 ms 70904 KB ans=YES N=196
42 Correct 38 ms 70904 KB ans=YES N=196
43 Correct 38 ms 70904 KB ans=YES N=195
44 Correct 76 ms 73976 KB ans=NO N=1934
45 Correct 52 ms 71928 KB ans=NO N=1965
46 Correct 75 ms 71416 KB ans=YES N=1824
47 Correct 81 ms 71416 KB ans=YES N=1981
48 Correct 72 ms 71288 KB ans=YES N=1814
49 Correct 83 ms 71544 KB ans=YES N=1854
50 Correct 74 ms 71292 KB ans=YES N=1831
51 Correct 79 ms 71424 KB ans=YES N=2000
52 Correct 79 ms 71544 KB ans=YES N=1847
53 Correct 81 ms 71704 KB ans=YES N=1819
54 Correct 86 ms 71416 KB ans=YES N=1986
55 Correct 112 ms 71928 KB ans=YES N=2000
56 Correct 122 ms 72060 KB ans=YES N=1834
57 Correct 115 ms 72056 KB ans=YES N=1860
58 Correct 120 ms 72148 KB ans=YES N=1898
59 Correct 99 ms 71892 KB ans=YES N=1832
60 Correct 148 ms 72440 KB ans=YES N=1929
61 Correct 78 ms 71544 KB ans=YES N=1919
62 Correct 112 ms 71928 KB ans=YES N=1882
63 Correct 146 ms 72440 KB ans=YES N=1922
64 Correct 84 ms 71544 KB ans=YES N=1989
65 Correct 136 ms 71932 KB ans=YES N=1978
66 Correct 117 ms 71928 KB ans=YES N=1867
67 Correct 107 ms 71864 KB ans=YES N=1942

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 73976 KB ans=NO N=1934
2 Correct 50 ms 71928 KB ans=NO N=1965
3 Correct 75 ms 71288 KB ans=YES N=1824
4 Correct 81 ms 71420 KB ans=YES N=1981
5 Correct 73 ms 71320 KB ans=YES N=1814
6 Correct 73 ms 71416 KB ans=YES N=1854
7 Correct 74 ms 71416 KB ans=YES N=1831
8 Correct 81 ms 71416 KB ans=YES N=2000
9 Correct 81 ms 71544 KB ans=YES N=1847
10 Correct 87 ms 71672 KB ans=YES N=1819
11 Correct 83 ms 71420 KB ans=YES N=1986
12 Correct 110 ms 71928 KB ans=YES N=2000
13 Correct 125 ms 72184 KB ans=YES N=1834
14 Correct 118 ms 72056 KB ans=YES N=1860
15 Correct 122 ms 72056 KB ans=YES N=1898
16 Correct 99 ms 71928 KB ans=YES N=1832
17 Correct 150 ms 72436 KB ans=YES N=1929
18 Correct 79 ms 71544 KB ans=YES N=1919
19 Correct 116 ms 71928 KB ans=YES N=1882
20 Correct 146 ms 72440 KB ans=YES N=1922
21 Correct 90 ms 71544 KB ans=YES N=1989
22 Correct 142 ms 71928 KB ans=YES N=1978
23 Correct 131 ms 71928 KB ans=YES N=1867

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 70776 KB ans=YES N=1
2 Correct 36 ms 70784 KB ans=YES N=4
3 Correct 37 ms 70780 KB ans=NO N=4
4 Correct 37 ms 70784 KB ans=YES N=5
5 Correct 37 ms 70776 KB ans=YES N=9
6 Correct 35 ms 70784 KB ans=YES N=5
7 Correct 37 ms 70780 KB ans=NO N=9
8 Correct 38 ms 70788 KB ans=NO N=10
9 Correct 37 ms 70776 KB ans=YES N=10
10 Correct 47 ms 70776 KB ans=YES N=10
11 Correct 38 ms 70776 KB ans=YES N=10
12 Correct 36 ms 70784 KB ans=YES N=9
13 Correct 36 ms 70784 KB ans=YES N=9
14 Correct 36 ms 70776 KB ans=YES N=8
15 Correct 37 ms 70776 KB ans=YES N=8
16 Correct 37 ms 70780 KB ans=NO N=2
17 Correct 36 ms 70776 KB ans=YES N=17
18 Correct 35 ms 70776 KB ans=YES N=25
19 Correct 37 ms 70776 KB ans=YES N=100
20 Correct 42 ms 70904 KB ans=YES N=185
21 Correct 39 ms 71032 KB ans=NO N=174
22 Correct 36 ms 70776 KB ans=YES N=90
23 Correct 36 ms 70776 KB ans=YES N=63
24 Correct 37 ms 70776 KB ans=YES N=87
25 Correct 37 ms 70784 KB ans=YES N=183
26 Correct 40 ms 70912 KB ans=YES N=188
27 Correct 51 ms 70904 KB ans=YES N=183
28 Correct 43 ms 70904 KB ans=YES N=189
29 Correct 37 ms 70904 KB ans=YES N=200
30 Correct 54 ms 70904 KB ans=YES N=190
31 Correct 38 ms 70912 KB ans=YES N=187
32 Correct 46 ms 70904 KB ans=YES N=187
33 Correct 37 ms 70912 KB ans=YES N=182
34 Correct 38 ms 70904 KB ans=YES N=184
35 Correct 39 ms 70904 KB ans=YES N=188
36 Correct 38 ms 70904 KB ans=YES N=181
37 Correct 39 ms 70904 KB ans=YES N=188
38 Correct 40 ms 70912 KB ans=YES N=191
39 Correct 37 ms 70904 KB ans=YES N=196
40 Correct 38 ms 70904 KB ans=YES N=196
41 Correct 37 ms 70904 KB ans=YES N=196
42 Correct 38 ms 70904 KB ans=YES N=196
43 Correct 38 ms 70904 KB ans=YES N=195
44 Correct 76 ms 73976 KB ans=NO N=1934
45 Correct 52 ms 71928 KB ans=NO N=1965
46 Correct 75 ms 71416 KB ans=YES N=1824
47 Correct 81 ms 71416 KB ans=YES N=1981
48 Correct 72 ms 71288 KB ans=YES N=1814
49 Correct 83 ms 71544 KB ans=YES N=1854
50 Correct 74 ms 71292 KB ans=YES N=1831
51 Correct 79 ms 71424 KB ans=YES N=2000
52 Correct 79 ms 71544 KB ans=YES N=1847
53 Correct 81 ms 71704 KB ans=YES N=1819
54 Correct 86 ms 71416 KB ans=YES N=1986
55 Correct 112 ms 71928 KB ans=YES N=2000
56 Correct 122 ms 72060 KB ans=YES N=1834
57 Correct 115 ms 72056 KB ans=YES N=1860
58 Correct 120 ms 72148 KB ans=YES N=1898
59 Correct 99 ms 71892 KB ans=YES N=1832
60 Correct 148 ms 72440 KB ans=YES N=1929
61 Correct 78 ms 71544 KB ans=YES N=1919
62 Correct 112 ms 71928 KB ans=YES N=1882
63 Correct 146 ms 72440 KB ans=YES N=1922
64 Correct 84 ms 71544 KB ans=YES N=1989
65 Correct 136 ms 71932 KB ans=YES N=1978
66 Correct 117 ms 71928 KB ans=YES N=1867
67 Correct 107 ms 71864 KB ans=YES N=1942
68 Correct 619 ms 92920 KB ans=NO N=66151
69 Correct 1757 ms 156424 KB ans=NO N=64333
70 Execution timed out 3573 ms 87168 KB Time limit exceeded
71 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 92792 KB ans=NO N=66151
2 Correct 1662 ms 156408 KB ans=NO N=64333
3 Execution timed out 3577 ms 87152 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 73976 KB ans=NO N=1934
2 Correct 50 ms 71928 KB ans=NO N=1965
3 Correct 75 ms 71288 KB ans=YES N=1824
4 Correct 81 ms 71420 KB ans=YES N=1981
5 Correct 73 ms 71320 KB ans=YES N=1814
6 Correct 73 ms 71416 KB ans=YES N=1854
7 Correct 74 ms 71416 KB ans=YES N=1831
8 Correct 81 ms 71416 KB ans=YES N=2000
9 Correct 81 ms 71544 KB ans=YES N=1847
10 Correct 87 ms 71672 KB ans=YES N=1819
11 Correct 83 ms 71420 KB ans=YES N=1986
12 Correct 110 ms 71928 KB ans=YES N=2000
13 Correct 125 ms 72184 KB ans=YES N=1834
14 Correct 118 ms 72056 KB ans=YES N=1860
15 Correct 122 ms 72056 KB ans=YES N=1898
16 Correct 99 ms 71928 KB ans=YES N=1832
17 Correct 150 ms 72436 KB ans=YES N=1929
18 Correct 79 ms 71544 KB ans=YES N=1919
19 Correct 116 ms 71928 KB ans=YES N=1882
20 Correct 146 ms 72440 KB ans=YES N=1922
21 Correct 90 ms 71544 KB ans=YES N=1989
22 Correct 142 ms 71928 KB ans=YES N=1978
23 Correct 131 ms 71928 KB ans=YES N=1867
24 Correct 551 ms 92792 KB ans=NO N=66151
25 Correct 1662 ms 156408 KB ans=NO N=64333
26 Execution timed out 3577 ms 87152 KB Time limit exceeded
27 Halted 0 ms 0 KB -