Submission #57480

ソースコード

?
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 << '\n';
}
else {
cout << v[s.root(x)]->find() << '\n';
}
}
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
corner_in1.txt AC 356 ms 33496 KB
1
corner_in2.txt AC 354 ms 33548 KB
1
corner_in3.txt AC 362 ms 33548 KB
1
corner_in4.txt AC 350 ms 33560 KB
1
corner_in5.txt AC 361 ms 33576 KB
1
large_in1.txt AC 544 ms 33696 KB
1
large_in2.txt AC 543 ms 33984 KB
1
large_in3.txt AC 544 ms 34220 KB
1
large_in4.txt AC 545 ms 34704 KB
1
large_in5.txt AC 545 ms 34840 KB
1
large_in6.txt AC 548 ms 34896 KB
1
sample_in1.txt AC 23 ms 1812 KB
1
sample_in2.txt AC 32 ms 1776 KB
1
small_in1.txt AC 20 ms 1864 KB
1
small_in2.txt AC 15 ms 1740 KB
1
small_in3.txt AC 15 ms 1868 KB
1
small_in4.txt AC 17 ms 1872 KB
1
small_in5.txt AC 18 ms 1756 KB
1
small_in6.txt AC 22 ms 1752 KB
1
small_in7.txt AC 17 ms 2016 KB
1
small_in8.txt AC 21 ms 2028 KB
1
small_in9.txt AC 32 ms 2032 KB
1
small_in10.txt AC 30 ms 1868 KB
1