oj.uz

Submission #1072963

# Submission time Handle Problem Language Result Execution time Memory
1072963 2024-08-24T07:52:20 Z emptypringlescan Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 385 ms 37084 KB 
#include <bits/stdc++.h>
using namespace std;
int dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
vector<pair<pair<int,int>,int> > adj[150005];
int v[150005];
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,t;
	cin >> n >> t;
	pair<pair<int,int>,int> arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i].first.first >> arr[i].first.second;
		arr[i].second=i;
	}
	set<pair<pair<int,int>,int> > got;
	set<pair<pair<int,int>,int> >::iterator it;
	for(int i=0; i<n; i++){
		for(int j=0; j<8; j++){
			pair<int,int> nx={arr[i].first.first+dx[j],arr[i].first.second+dy[j]};
			it=got.lower_bound({nx,-1});
			if(it==got.end()||it->first!=nx) continue;
			adj[i].push_back(*it);
			adj[it->second].push_back(arr[i]);
		}
		got.insert(arr[i]);
	}
	priority_queue<pair<pair<int,int>,int> > pq;
	pq.push(arr[0]);
	vector<int> ans;
	while(!pq.empty()){
		int y=pq.top().second;
		pq.pop();
		if(v[y]) continue;
		v[y]=1;
		ans.push_back(y);
		for(auto i:adj[y]){
			if(!v[i.second]) pq.push(i);
		}
	}
	if((int)ans.size()!=n){
		cout << "NO";
	}
	else{
		cout << "YES\n";
		for(int i:ans) cout << i+1 << ' ' ;
	}
}

Subtask #1
8.0 / 8.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB ans=YES N=1
2 Correct 2 ms 3932 KB ans=YES N=4
3 Correct 2 ms 3932 KB ans=NO N=4
4 Correct 2 ms 3932 KB ans=YES N=5
5 Correct 2 ms 3932 KB ans=YES N=9
6 Correct 1 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 2 ms 3928 KB ans=NO N=10
9 Correct 1 ms 3932 KB ans=YES N=10
10 Correct 2 ms 3932 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 1 ms 3932 KB ans=YES N=9
13 Correct 1 ms 3932 KB ans=YES N=9
14 Correct 2 ms 3932 KB ans=YES N=8
15 Correct 1 ms 3932 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Correct 2 ms 3932 KB ans=YES N=17
18 Correct 2 ms 3932 KB ans=YES N=25
19 Correct 2 ms 3988 KB ans=YES N=100
20 Correct 2 ms 3932 KB ans=YES N=185
21 Correct 2 ms 3932 KB ans=NO N=174
22 Correct 2 ms 3932 KB ans=YES N=90
23 Correct 2 ms 3932 KB ans=YES N=63
24 Correct 2 ms 3932 KB ans=YES N=87
25 Correct 3 ms 3932 KB ans=YES N=183
26 Correct 3 ms 3932 KB ans=YES N=188
27 Correct 2 ms 3932 KB ans=YES N=183
28 Correct 2 ms 4032 KB ans=YES N=189
29 Correct 2 ms 3928 KB ans=YES N=200
30 Correct 2 ms 3928 KB ans=YES N=190
31 Correct 2 ms 3932 KB ans=YES N=187
32 Correct 2 ms 3932 KB ans=YES N=187
33 Correct 2 ms 3932 KB ans=YES N=182
34 Correct 2 ms 3932 KB ans=YES N=184
35 Correct 2 ms 3948 KB ans=YES N=188
36 Correct 2 ms 3932 KB ans=YES N=181
37 Correct 2 ms 3928 KB ans=YES N=188
38 Correct 2 ms 3932 KB ans=YES N=191
39 Correct 2 ms 3928 KB ans=YES N=196
40 Correct 2 ms 3932 KB ans=YES N=196
41 Correct 2 ms 3932 KB ans=YES N=196
42 Correct 2 ms 3932 KB ans=YES N=196
43 Correct 2 ms 3932 KB ans=YES N=195
44 Correct 3 ms 3928 KB ans=NO N=1934
45 Correct 3 ms 4188 KB ans=NO N=1965
46 Correct 4 ms 4188 KB ans=YES N=1824
47 Correct 4 ms 4188 KB ans=YES N=1981
48 Correct 5 ms 4188 KB ans=YES N=1814
49 Correct 4 ms 4188 KB ans=YES N=1854
50 Correct 4 ms 4188 KB ans=YES N=1831
51 Correct 4 ms 4188 KB ans=YES N=2000
52 Correct 4 ms 4188 KB ans=YES N=1847
53 Correct 3 ms 4188 KB ans=YES N=1819
54 Correct 4 ms 4188 KB ans=YES N=1986
55 Correct 4 ms 4188 KB ans=YES N=2000
56 Correct 4 ms 4188 KB ans=YES N=1834
57 Correct 5 ms 4188 KB ans=YES N=1860
58 Correct 4 ms 4184 KB ans=YES N=1898
59 Correct 4 ms 4304 KB ans=YES N=1832
60 Correct 4 ms 4188 KB ans=YES N=1929
61 Correct 4 ms 4184 KB ans=YES N=1919
62 Correct 3 ms 4188 KB ans=YES N=1882
63 Correct 3 ms 4188 KB ans=YES N=1922
64 Correct 5 ms 4440 KB ans=YES N=1989
65 Correct 3 ms 4184 KB ans=YES N=1978
66 Correct 4 ms 4148 KB ans=YES N=1867
67 Correct 4 ms 4188 KB ans=YES N=1942

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3932 KB ans=NO N=1934
2 Correct 3 ms 4188 KB ans=NO N=1965
3 Incorrect 5 ms 4188 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 974)
4 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3932 KB ans=YES N=1
2 Correct 2 ms 3932 KB ans=YES N=4
3 Correct 2 ms 3932 KB ans=NO N=4
4 Correct 2 ms 3932 KB ans=YES N=5
5 Correct 2 ms 3932 KB ans=YES N=9
6 Correct 1 ms 3932 KB ans=YES N=5
7 Correct 2 ms 3932 KB ans=NO N=9
8 Correct 2 ms 3928 KB ans=NO N=10
9 Correct 1 ms 3932 KB ans=YES N=10
10 Correct 2 ms 3932 KB ans=YES N=10
11 Correct 2 ms 3932 KB ans=YES N=10
12 Correct 1 ms 3932 KB ans=YES N=9
13 Correct 1 ms 3932 KB ans=YES N=9
14 Correct 2 ms 3932 KB ans=YES N=8
15 Correct 1 ms 3932 KB ans=YES N=8
16 Correct 2 ms 3932 KB ans=NO N=2
17 Correct 2 ms 3932 KB ans=YES N=17
18 Correct 2 ms 3932 KB ans=YES N=25
19 Correct 2 ms 3988 KB ans=YES N=100
20 Correct 2 ms 3932 KB ans=YES N=185
21 Correct 2 ms 3932 KB ans=NO N=174
22 Correct 2 ms 3932 KB ans=YES N=90
23 Correct 2 ms 3932 KB ans=YES N=63
24 Correct 2 ms 3932 KB ans=YES N=87
25 Correct 3 ms 3932 KB ans=YES N=183
26 Correct 3 ms 3932 KB ans=YES N=188
27 Correct 2 ms 3932 KB ans=YES N=183
28 Correct 2 ms 4032 KB ans=YES N=189
29 Correct 2 ms 3928 KB ans=YES N=200
30 Correct 2 ms 3928 KB ans=YES N=190
31 Correct 2 ms 3932 KB ans=YES N=187
32 Correct 2 ms 3932 KB ans=YES N=187
33 Correct 2 ms 3932 KB ans=YES N=182
34 Correct 2 ms 3932 KB ans=YES N=184
35 Correct 2 ms 3948 KB ans=YES N=188
36 Correct 2 ms 3932 KB ans=YES N=181
37 Correct 2 ms 3928 KB ans=YES N=188
38 Correct 2 ms 3932 KB ans=YES N=191
39 Correct 2 ms 3928 KB ans=YES N=196
40 Correct 2 ms 3932 KB ans=YES N=196
41 Correct 2 ms 3932 KB ans=YES N=196
42 Correct 2 ms 3932 KB ans=YES N=196
43 Correct 2 ms 3932 KB ans=YES N=195
44 Correct 3 ms 3928 KB ans=NO N=1934
45 Correct 3 ms 4188 KB ans=NO N=1965
46 Correct 4 ms 4188 KB ans=YES N=1824
47 Correct 4 ms 4188 KB ans=YES N=1981
48 Correct 5 ms 4188 KB ans=YES N=1814
49 Correct 4 ms 4188 KB ans=YES N=1854
50 Correct 4 ms 4188 KB ans=YES N=1831
51 Correct 4 ms 4188 KB ans=YES N=2000
52 Correct 4 ms 4188 KB ans=YES N=1847
53 Correct 3 ms 4188 KB ans=YES N=1819
54 Correct 4 ms 4188 KB ans=YES N=1986
55 Correct 4 ms 4188 KB ans=YES N=2000
56 Correct 4 ms 4188 KB ans=YES N=1834
57 Correct 5 ms 4188 KB ans=YES N=1860
58 Correct 4 ms 4184 KB ans=YES N=1898
59 Correct 4 ms 4304 KB ans=YES N=1832
60 Correct 4 ms 4188 KB ans=YES N=1929
61 Correct 4 ms 4184 KB ans=YES N=1919
62 Correct 3 ms 4188 KB ans=YES N=1882
63 Correct 3 ms 4188 KB ans=YES N=1922
64 Correct 5 ms 4440 KB ans=YES N=1989
65 Correct 3 ms 4184 KB ans=YES N=1978
66 Correct 4 ms 4148 KB ans=YES N=1867
67 Correct 4 ms 4188 KB ans=YES N=1942
68 Correct 124 ms 16596 KB ans=NO N=66151
69 Correct 75 ms 10060 KB ans=NO N=64333
70 Correct 151 ms 18400 KB ans=YES N=69316
71 Correct 127 ms 17880 KB ans=YES N=66695
72 Correct 132 ms 18128 KB ans=YES N=68436
73 Correct 148 ms 18400 KB ans=YES N=70000
74 Correct 135 ms 18388 KB ans=YES N=68501
75 Correct 147 ms 18412 KB ans=YES N=70000
76 Correct 118 ms 17904 KB ans=YES N=65009
77 Correct 107 ms 15072 KB ans=YES N=67007
78 Correct 101 ms 14280 KB ans=YES N=66357
79 Correct 97 ms 13780 KB ans=YES N=65430
80 Correct 102 ms 13784 KB ans=YES N=65790
81 Correct 105 ms 14300 KB ans=YES N=66020
82 Correct 107 ms 14920 KB ans=YES N=65809
83 Correct 160 ms 17100 KB ans=YES N=65651
84 Correct 100 ms 13008 KB ans=YES N=68040
85 Correct 99 ms 13776 KB ans=YES N=66570
86 Correct 129 ms 17360 KB ans=YES N=65421
87 Correct 134 ms 17916 KB ans=YES N=68351
88 Correct 132 ms 17976 KB ans=YES N=67027
89 Correct 70 ms 12956 KB ans=YES N=68879
90 Correct 122 ms 16848 KB ans=YES N=67256
91 Correct 343 ms 34804 KB ans=YES N=148315
92 Correct 180 ms 16756 KB ans=NO N=142745
93 Correct 118 ms 17976 KB ans=NO N=148443
94 Correct 349 ms 36544 KB ans=YES N=148328
95 Correct 360 ms 36548 KB ans=YES N=147855
96 Correct 352 ms 37084 KB ans=YES N=150000
97 Correct 343 ms 35880 KB ans=YES N=144725
98 Correct 385 ms 36956 KB ans=YES N=149445
99 Correct 352 ms 35780 KB ans=YES N=144455
100 Correct 331 ms 35596 KB ans=YES N=143487
101 Correct 362 ms 36880 KB ans=YES N=149688
102 Correct 265 ms 28612 KB ans=YES N=141481
103 Correct 232 ms 26820 KB ans=YES N=147430
104 Correct 309 ms 30440 KB ans=YES N=142247
105 Correct 326 ms 31568 KB ans=YES N=149941
106 Correct 230 ms 26868 KB ans=YES N=141635
107 Correct 257 ms 27256 KB ans=YES N=142896
108 Correct 256 ms 25792 KB ans=YES N=142069
109 Correct 358 ms 34076 KB ans=YES N=142378
110 Correct 305 ms 31448 KB ans=YES N=150000
111 Correct 237 ms 24020 KB ans=YES N=141452
112 Correct 242 ms 22796 KB ans=YES N=134453
113 Correct 179 ms 24952 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 16592 KB ans=NO N=66151
2 Correct 71 ms 10068 KB ans=NO N=64333
3 Incorrect 132 ms 18396 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 51180)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3932 KB ans=NO N=1934
2 Correct 3 ms 4188 KB ans=NO N=1965
3 Incorrect 5 ms 4188 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 974)
4 Halted 0 ms 0 KB -