Submission #57495

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <functional>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
using namespace std;
using llong = long long;
//===
template<class T, class Compare = function<bool(T, T)>,
class Heap = priority_queue<T, vector<T>, Compare> >
struct FindKth {
const int K;
Heap maxh;
Heap minh;
FindKth (const int K, const Compare &cmp = less<T>()):
K(K),
maxh(cmp),
minh([cmp](T l, T r){ return cmp(r, l); })
{};
size_t size() {
return maxh.size() + minh.size();
};
bool empty() {
return size() <= 0;
};
void push(T d){
maxh.push(d);
if (maxh.size() > K) {
minh.push(maxh.top());
maxh.pop();
}
};
T find(){
assert(maxh.size() == K);
return maxh.top();
};
T find_lower(){
assert(!empty());
return maxh.top();
};
void pop() {
assert(!empty());
maxh.pop();
if (!minh.empty()) {
maxh.push(minh.top());
minh.pop();
}
};
void merge_with(FindKth<T, Compare, Heap> &x) {
while (!x.empty()) {
push(x.find_lower());
x.pop();
}
};
};
//===
//===
struct UnionFind {
int n;
map<int, int> parent;
int root(int x) {
if (parent[x] < 0) {
return x;
}
return parent[x] = root(parent[x]);
};
bool same(int x, int y) {
return root(x) == root(y);
};
int size(int x) {
return -(parent[root(x)]);
};
void unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y) return;
parent[x] += parent[y];
parent[y] = x;
return;
};
};
//===
UnionFind s;
map<llong, FindKth<llong>*> v;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
llong n, m, k;
llong arr[100005];
llong com, x, y;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
v[arr[i]] = new FindKth<llong>(k);
v[arr[i]]->push(arr[i]);
s.parent[arr[i]] = -1;
}
for (int i = 0; i < m; i++) {
cin >> com;
if (com == 1) {
cin >> x >> y;
if (s.same(x, y)) continue;
if (s.size(x) > s.size(y)) {
v[s.root(x)]->merge_with(*v[s.root(y)]);
s.unite(x, y);
}
else {
v[s.root(y)]->merge_with(*v[s.root(x)]);
s.unite(y, x);
}
}
else if (com == 2) {
cin >> x;
if (v[s.root(x)]->size() < k) {
cout << -1 << endl;
}
else {
cout << v[s.root(x)]->find() << endl;
}
}
}
return 0;
}

ステータス

項目 データ
問題 1232 - Corner Kth ⇔ Corner Case
ユーザー名 ei1710
投稿日時 2019-12-17 20:50:54
言語 C++14
状態 Accepted
得点 100
ソースコード長 3166 Byte
最大実行時間 491 ms
最大メモリ使用量 34960 KB

セット

セット 得点 Cases
1 ALL 100 / 100 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
corner_in1.txt AC 319 ms 33620 KB
1
corner_in2.txt AC 310 ms 33516 KB
1
corner_in3.txt AC 304 ms 33484 KB
1
corner_in4.txt AC 305 ms 33604 KB
1
corner_in5.txt AC 318 ms 33604 KB
1
large_in1.txt AC 488 ms 33848 KB
1
large_in2.txt AC 482 ms 33920 KB
1
large_in3.txt AC 491 ms 34132 KB
1
large_in4.txt AC 488 ms 34492 KB
1
large_in5.txt AC 491 ms 34664 KB
1
large_in6.txt AC 489 ms 34960 KB
1
sample_in1.txt AC 35 ms 1852 KB
1
sample_in2.txt AC 21 ms 1920 KB
1
small_in1.txt AC 19 ms 1992 KB
1
small_in2.txt AC 19 ms 1960 KB
1
small_in3.txt AC 20 ms 2076 KB
1
small_in4.txt AC 21 ms 1936 KB
1
small_in5.txt AC 24 ms 1928 KB
1
small_in6.txt AC 21 ms 2032 KB
1
small_in7.txt AC 21 ms 1892 KB
1
small_in8.txt AC 19 ms 1888 KB
1
small_in9.txt AC 17 ms 1876 KB
1
small_in10.txt AC 18 ms 1980 KB
1