oj.uz

Submission #447183

# Submission time Handle Problem Language Result Execution time Memory
447183 2021-07-25T03:26:51 Z 8e7 Building Skyscrapers (CEOI19_skyscrapers) C++17
51 / 100
 3500 ms 24032 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
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 150005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
unordered_map<ll, int> mp;
unordered_set<ll> bfs, cand;
ll h(pii p) {
	return (((ll)p.ff)<<30) + p.ss;
}
pii pos[maxn];
bool vis[maxn], out[maxn], art[maxn], used[maxn];
vector<int> adj[maxn];
void dfs(int n) {
	int x = pos[n].ff, y = pos[n].ss;
	vis[n] = 1;
	for (int dx = -1;dx <= 1;dx++) {
		for (int dy = -1;dy <= 1;dy++) {
			pii to = {x + dx, y + dy};
			cand.insert(h(to));
			if (dx == 0 && dy == 0) continue;
			int v = mp[h(to)];
			if (v) {
				if (!vis[v]) dfs(v);
				adj[n].push_back(v);
			}
		}
	}
}
int ans[maxn], low[maxn], ti[maxn];
int c = 0;
void dfs2(int n, int par, int root) {
	vis[n] = 1;
	low[n] = ti[n] = c++;
	int p = ti[n], chi = 0, val = 0;
	for (int v:adj[n]) {
		if (used[v]) continue;
		if (!vis[v]) {
			chi++;
			dfs2(v, n, root);
			low[n] = min(low[n], low[v]);
			val = max(val, low[v]);
		} else if (v != par) {
			p = min(p, ti[v]);
		}
	}
	if ((n != root && chi && val >= ti[n]) || (n == root && chi > 1)) art[n] = 1;
	low[n] = min(low[n], p);
}
int main() {
	io
	int n, type;
	cin >> n >> type;
	int mx = 1<<30, my = 1<<30, st = 0;
	for (int i = 1;i <= n;i++) {
		cin >> pos[i].ff >> pos[i].ss;
		mx = min(mx, pos[i].ff);
		if (pos[i].ss < my) {
			my = pos[i].ss;
			st = pos[i].ff;
		}
	}
	for (int i = 1;i <= n;i++) {
		pos[i] = {pos[i].ff - mx + 1, pos[i].ss - my + 1};
		mp[h(pos[i])] = i;
	}
	dfs(1);
	for (int i = 1;i <= n;i++) {
		if (!vis[i]) {
			cout << "NO" << endl;
			return 0;
		}
		vis[i] = 0;
	}
	queue<pii> que;
	que.push({st - mx + 1, 0});
	bfs.insert(h(que.front()));
	for (int it = 0;it < n;it++) {
		while (que.size()) {
			pii cur = que.front();que.pop();
			for (int k = 0;k < 4;k++) {
				pii ne = {cur.ff + dir[k][0], cur.ss + dir[k][1]};
				ll x = h(ne);
				if (ne.ff >= 0 && ne.ss >= 0) {
					int v = mp[x];
					if (v) out[v] = 1;
					else {
						if (cand.find(x) != cand.end() && bfs.find(x) == bfs.end()) {
							bfs.insert(x);
							que.push(ne);
						}	
					}
				}
			}
		}
		for (int j = n;j >= 1;j--) art[j] = 0, vis[j] = 0, low[j] = ti[j] = 0;	
		c = 0;
		for (int j = n;j >= 1;j--) {
			if (!used[j]) {
				dfs2(j, 0, j);
				break;
			}
		}	
		//pary(art + 1, art + n + 1);
		for (int j = n;j >= 1;j--) {
			if (!used[j] && !art[j] && out[j]) {
				ans[it] = j;
				//cout << j<< endl;
				que.push(pos[j]);
				bfs.insert(h(pos[j]));
				used[j] = 1;
				break;
			}
		}
	}
	cout << "YES" << endl;
	for (int i = n - 1;i >= 0;i--) cout << ans[i] << "\n";
}
/*
 
3
2
0 0
0 1
0 2
 
9
1
-5 -5
-4 -6
-3 -7
-2 -6
-1 -5
-2 -4
-3 -3
-4 -4
-3 -5
 
7 1
0 4
0 5
0 3
0 2
0 7
0 1
0 6
*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 3 ms 3788 KB ans=YES N=4
3 Correct 2 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Correct 2 ms 3856 KB ans=YES N=9
6 Correct 2 ms 3788 KB ans=YES N=5
7 Correct 3 ms 3788 KB ans=NO N=9
8 Correct 2 ms 3788 KB ans=NO N=10
9 Correct 2 ms 3788 KB ans=YES N=10
10 Correct 2 ms 3788 KB ans=YES N=10
11 Correct 2 ms 3856 KB ans=YES N=10
12 Correct 2 ms 3788 KB ans=YES N=9
13 Correct 2 ms 3848 KB ans=YES N=9
14 Correct 2 ms 3788 KB ans=YES N=8
15 Correct 2 ms 3788 KB ans=YES N=8
16 Correct 2 ms 3788 KB ans=NO N=2

Subtask #2
14.0 / 14.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 3 ms 3788 KB ans=YES N=4
3 Correct 2 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Correct 2 ms 3856 KB ans=YES N=9
6 Correct 2 ms 3788 KB ans=YES N=5
7 Correct 3 ms 3788 KB ans=NO N=9
8 Correct 2 ms 3788 KB ans=NO N=10
9 Correct 2 ms 3788 KB ans=YES N=10
10 Correct 2 ms 3788 KB ans=YES N=10
11 Correct 2 ms 3856 KB ans=YES N=10
12 Correct 2 ms 3788 KB ans=YES N=9
13 Correct 2 ms 3848 KB ans=YES N=9
14 Correct 2 ms 3788 KB ans=YES N=8
15 Correct 2 ms 3788 KB ans=YES N=8
16 Correct 2 ms 3788 KB ans=NO N=2
17 Correct 3 ms 3788 KB ans=YES N=17
18 Correct 3 ms 3788 KB ans=YES N=25
19 Correct 4 ms 3916 KB ans=YES N=100
20 Correct 3 ms 3852 KB ans=YES N=185
21 Correct 3 ms 3856 KB ans=NO N=174
22 Correct 3 ms 3788 KB ans=YES N=90
23 Correct 3 ms 3788 KB ans=YES N=63
24 Correct 3 ms 3848 KB ans=YES N=87
25 Correct 3 ms 3852 KB ans=YES N=183
26 Correct 4 ms 3856 KB ans=YES N=188
27 Correct 4 ms 3916 KB ans=YES N=183
28 Correct 4 ms 3856 KB ans=YES N=189
29 Correct 4 ms 3916 KB ans=YES N=200
30 Correct 3 ms 3916 KB ans=YES N=190
31 Correct 4 ms 3860 KB ans=YES N=187
32 Correct 5 ms 3916 KB ans=YES N=187
33 Correct 4 ms 3916 KB ans=YES N=182
34 Correct 4 ms 3916 KB ans=YES N=184
35 Correct 4 ms 3916 KB ans=YES N=188
36 Correct 3 ms 3916 KB ans=YES N=181
37 Correct 4 ms 3920 KB ans=YES N=188
38 Correct 4 ms 3916 KB ans=YES N=191
39 Correct 3 ms 3916 KB ans=YES N=196
40 Correct 3 ms 3916 KB ans=YES N=196
41 Correct 3 ms 3916 KB ans=YES N=196
42 Correct 3 ms 3916 KB ans=YES N=196
43 Correct 4 ms 3916 KB ans=YES N=195
44 Correct 3 ms 3916 KB ans=NO N=1934
45 Correct 3 ms 3916 KB ans=NO N=1965
46 Correct 81 ms 4428 KB ans=YES N=1824
47 Correct 102 ms 4548 KB ans=YES N=1981
48 Correct 81 ms 4416 KB ans=YES N=1814
49 Correct 93 ms 4584 KB ans=YES N=1854
50 Correct 87 ms 4480 KB ans=YES N=1831
51 Correct 104 ms 4524 KB ans=YES N=2000
52 Correct 78 ms 4572 KB ans=YES N=1847
53 Correct 69 ms 4652 KB ans=YES N=1819
54 Correct 106 ms 4620 KB ans=YES N=1986
55 Correct 85 ms 4948 KB ans=YES N=2000
56 Correct 72 ms 4964 KB ans=YES N=1834
57 Correct 69 ms 4984 KB ans=YES N=1860
58 Correct 72 ms 4932 KB ans=YES N=1898
59 Correct 75 ms 4660 KB ans=YES N=1832
60 Correct 67 ms 5200 KB ans=YES N=1929
61 Correct 98 ms 4548 KB ans=YES N=1919
62 Correct 82 ms 4900 KB ans=YES N=1882
63 Correct 79 ms 5200 KB ans=YES N=1922
64 Correct 80 ms 4676 KB ans=YES N=1989
65 Correct 56 ms 4752 KB ans=YES N=1978
66 Correct 63 ms 4952 KB ans=YES N=1867
67 Correct 83 ms 4716 KB ans=YES N=1942

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3916 KB ans=NO N=1934
2 Correct 3 ms 3916 KB ans=NO N=1965
3 Correct 82 ms 4408 KB ans=YES N=1824
4 Correct 114 ms 4516 KB ans=YES N=1981
5 Correct 84 ms 4440 KB ans=YES N=1814
6 Correct 92 ms 4496 KB ans=YES N=1854
7 Correct 114 ms 4488 KB ans=YES N=1831
8 Correct 105 ms 4552 KB ans=YES N=2000
9 Correct 79 ms 4668 KB ans=YES N=1847
10 Correct 84 ms 4540 KB ans=YES N=1819
11 Correct 107 ms 4664 KB ans=YES N=1986
12 Correct 82 ms 4932 KB ans=YES N=2000
13 Correct 63 ms 4872 KB ans=YES N=1834
14 Correct 67 ms 4876 KB ans=YES N=1860
15 Correct 78 ms 4896 KB ans=YES N=1898
16 Correct 82 ms 4804 KB ans=YES N=1832
17 Correct 66 ms 5200 KB ans=YES N=1929
18 Correct 113 ms 4484 KB ans=YES N=1919
19 Correct 75 ms 4932 KB ans=YES N=1882
20 Correct 62 ms 5196 KB ans=YES N=1922
21 Correct 86 ms 4676 KB ans=YES N=1989
22 Correct 59 ms 4756 KB ans=YES N=1978
23 Correct 64 ms 4932 KB ans=YES N=1867

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB ans=YES N=1
2 Correct 3 ms 3788 KB ans=YES N=4
3 Correct 2 ms 3788 KB ans=NO N=4
4 Correct 3 ms 3788 KB ans=YES N=5
5 Correct 2 ms 3856 KB ans=YES N=9
6 Correct 2 ms 3788 KB ans=YES N=5
7 Correct 3 ms 3788 KB ans=NO N=9
8 Correct 2 ms 3788 KB ans=NO N=10
9 Correct 2 ms 3788 KB ans=YES N=10
10 Correct 2 ms 3788 KB ans=YES N=10
11 Correct 2 ms 3856 KB ans=YES N=10
12 Correct 2 ms 3788 KB ans=YES N=9
13 Correct 2 ms 3848 KB ans=YES N=9
14 Correct 2 ms 3788 KB ans=YES N=8
15 Correct 2 ms 3788 KB ans=YES N=8
16 Correct 2 ms 3788 KB ans=NO N=2
17 Correct 3 ms 3788 KB ans=YES N=17
18 Correct 3 ms 3788 KB ans=YES N=25
19 Correct 4 ms 3916 KB ans=YES N=100
20 Correct 3 ms 3852 KB ans=YES N=185
21 Correct 3 ms 3856 KB ans=NO N=174
22 Correct 3 ms 3788 KB ans=YES N=90
23 Correct 3 ms 3788 KB ans=YES N=63
24 Correct 3 ms 3848 KB ans=YES N=87
25 Correct 3 ms 3852 KB ans=YES N=183
26 Correct 4 ms 3856 KB ans=YES N=188
27 Correct 4 ms 3916 KB ans=YES N=183
28 Correct 4 ms 3856 KB ans=YES N=189
29 Correct 4 ms 3916 KB ans=YES N=200
30 Correct 3 ms 3916 KB ans=YES N=190
31 Correct 4 ms 3860 KB ans=YES N=187
32 Correct 5 ms 3916 KB ans=YES N=187
33 Correct 4 ms 3916 KB ans=YES N=182
34 Correct 4 ms 3916 KB ans=YES N=184
35 Correct 4 ms 3916 KB ans=YES N=188
36 Correct 3 ms 3916 KB ans=YES N=181
37 Correct 4 ms 3920 KB ans=YES N=188
38 Correct 4 ms 3916 KB ans=YES N=191
39 Correct 3 ms 3916 KB ans=YES N=196
40 Correct 3 ms 3916 KB ans=YES N=196
41 Correct 3 ms 3916 KB ans=YES N=196
42 Correct 3 ms 3916 KB ans=YES N=196
43 Correct 4 ms 3916 KB ans=YES N=195
44 Correct 3 ms 3916 KB ans=NO N=1934
45 Correct 3 ms 3916 KB ans=NO N=1965
46 Correct 81 ms 4428 KB ans=YES N=1824
47 Correct 102 ms 4548 KB ans=YES N=1981
48 Correct 81 ms 4416 KB ans=YES N=1814
49 Correct 93 ms 4584 KB ans=YES N=1854
50 Correct 87 ms 4480 KB ans=YES N=1831
51 Correct 104 ms 4524 KB ans=YES N=2000
52 Correct 78 ms 4572 KB ans=YES N=1847
53 Correct 69 ms 4652 KB ans=YES N=1819
54 Correct 106 ms 4620 KB ans=YES N=1986
55 Correct 85 ms 4948 KB ans=YES N=2000
56 Correct 72 ms 4964 KB ans=YES N=1834
57 Correct 69 ms 4984 KB ans=YES N=1860
58 Correct 72 ms 4932 KB ans=YES N=1898
59 Correct 75 ms 4660 KB ans=YES N=1832
60 Correct 67 ms 5200 KB ans=YES N=1929
61 Correct 98 ms 4548 KB ans=YES N=1919
62 Correct 82 ms 4900 KB ans=YES N=1882
63 Correct 79 ms 5200 KB ans=YES N=1922
64 Correct 80 ms 4676 KB ans=YES N=1989
65 Correct 56 ms 4752 KB ans=YES N=1978
66 Correct 63 ms 4952 KB ans=YES N=1867
67 Correct 83 ms 4716 KB ans=YES N=1942
68 Correct 112 ms 23784 KB ans=NO N=66151
69 Correct 26 ms 7468 KB ans=NO N=64333
70 Execution timed out 3546 ms 24032 KB Time limit exceeded
71 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 23260 KB ans=NO N=66151
2 Correct 29 ms 6968 KB ans=NO N=64333
3 Execution timed out 3558 ms 23476 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3916 KB ans=NO N=1934
2 Correct 3 ms 3916 KB ans=NO N=1965
3 Correct 82 ms 4408 KB ans=YES N=1824
4 Correct 114 ms 4516 KB ans=YES N=1981
5 Correct 84 ms 4440 KB ans=YES N=1814
6 Correct 92 ms 4496 KB ans=YES N=1854
7 Correct 114 ms 4488 KB ans=YES N=1831
8 Correct 105 ms 4552 KB ans=YES N=2000
9 Correct 79 ms 4668 KB ans=YES N=1847
10 Correct 84 ms 4540 KB ans=YES N=1819
11 Correct 107 ms 4664 KB ans=YES N=1986
12 Correct 82 ms 4932 KB ans=YES N=2000
13 Correct 63 ms 4872 KB ans=YES N=1834
14 Correct 67 ms 4876 KB ans=YES N=1860
15 Correct 78 ms 4896 KB ans=YES N=1898
16 Correct 82 ms 4804 KB ans=YES N=1832
17 Correct 66 ms 5200 KB ans=YES N=1929
18 Correct 113 ms 4484 KB ans=YES N=1919
19 Correct 75 ms 4932 KB ans=YES N=1882
20 Correct 62 ms 5196 KB ans=YES N=1922
21 Correct 86 ms 4676 KB ans=YES N=1989
22 Correct 59 ms 4756 KB ans=YES N=1978
23 Correct 64 ms 4932 KB ans=YES N=1867
24 Correct 113 ms 23260 KB ans=NO N=66151
25 Correct 29 ms 6968 KB ans=NO N=64333
26 Execution timed out 3558 ms 23476 KB Time limit exceeded
27 Halted 0 ms 0 KB -