답안 #447183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
447183	2021-07-25T03:26:51 Z	8e7	Building Skyscrapers (CEOI19_skyscrapers)	C++17	51 / 100	3500 ms	24032 KB

skyscrapers

//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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-