Submission #57493

ソースコード

?
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
#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() {
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:49:45
言語 C++14
状態 Accepted
得点 100
ソースコード長 3083 Byte
最大実行時間 550 ms
最大メモリ使用量 34888 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
corner_in1.txt AC 360 ms 33496 KB
1
corner_in2.txt AC 359 ms 33416 KB
1
corner_in3.txt AC 363 ms 33408 KB
1
corner_in4.txt AC 353 ms 33424 KB
1
corner_in5.txt AC 350 ms 33440 KB
1
large_in1.txt AC 536 ms 33684 KB
1
large_in2.txt AC 536 ms 33848 KB
1
large_in3.txt AC 542 ms 34080 KB
1
large_in4.txt AC 550 ms 34564 KB
1
large_in5.txt AC 546 ms 34700 KB
1
large_in6.txt AC 544 ms 34888 KB
1
sample_in1.txt AC 29 ms 1796 KB
1
sample_in2.txt AC 31 ms 1756 KB
1
small_in1.txt AC 21 ms 1852 KB
1
small_in2.txt AC 22 ms 1860 KB
1
small_in3.txt AC 22 ms 1868 KB
1
small_in4.txt AC 25 ms 1872 KB
1
small_in5.txt AC 22 ms 1888 KB
1
small_in6.txt AC 21 ms 1892 KB
1
small_in7.txt AC 21 ms 1904 KB
1
small_in8.txt AC 24 ms 1916 KB
1
small_in9.txt AC 21 ms 1920 KB
1
small_in10.txt AC 18 ms 1988 KB
1