Submission #57477

ソースコード

?
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
155
156
#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) {
if (size() < x.size()) {
while (!empty()) {
x.push(find_lower());
pop();
}
}
else {
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;
if (parent[y] < parent[x]) swap(x, y);
parent[x] += parent[y];
parent[y] = x;
return;
};
};
//===
UnionFind s;
map<llong, FindKth<llong>*> v;
int main() {
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;
v[s.root(x)]->merge_with(*v[s.root(y)]);
s.unite(x, y);
}
else if (com == 2) {
cin >> x;
if (v[s.root(x)]->size() < k) {
cout << -1 << '\n';
}
else {
cout << v[s.root(x)]->find() << '\n';
}
}
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
corner_in1.txt AC 326 ms 33496 KB
1
corner_in2.txt AC 324 ms 33416 KB
1
corner_in3.txt AC 333 ms 33404 KB
1
corner_in4.txt AC 331 ms 33288 KB
1
corner_in5.txt AC 334 ms 33304 KB
1
large_in1.txt AC 515 ms 33812 KB
1
large_in2.txt AC 555 ms 33844 KB
1
large_in3.txt AC 516 ms 33952 KB
1
large_in4.txt AC 537 ms 34560 KB
1
large_in5.txt AC 557 ms 34696 KB
1
large_in6.txt AC 533 ms 34884 KB
1
sample_in1.txt AC 17 ms 1800 KB
1
sample_in2.txt AC 20 ms 1628 KB
1
small_in1.txt AC 20 ms 1724 KB
1
small_in2.txt AC 17 ms 1992 KB
1
small_in3.txt AC 16 ms 1996 KB
1
small_in4.txt AC 21 ms 1876 KB
1
small_in5.txt AC 22 ms 2008 KB
1
small_in6.txt AC 18 ms 2008 KB
1
small_in7.txt AC 18 ms 1880 KB
1
small_in8.txt AC 17 ms 1896 KB
1
small_in9.txt AC 17 ms 1904 KB
1
small_in10.txt AC 18 ms 1864 KB
1