Submission #66706

ソースコード

?
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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#include <bits/stdc++.h>
#define all(v) std::begin(v), std::end(v)
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
template <typename T, typename U>
bool chmin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template <typename T, typename U>
bool chmax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
template <typename T>
class Compressor {
std::vector<T> values;
std::unordered_map<T, size_t> indexes;
public:
template <class InputItr>
explicit Compressor(InputItr begin, InputItr end)
: values(begin, end)
{}
void build() {
std::sort(all(values));
values.erase(std::unique(all(values)), std::end(values));
rep(i, 0, int(values.size())) {
indexes[values[i]] = i;
}
}
inline void insert(const T &value) { values.push_back(value); }
inline size_t size() const { return values.size(); }
inline size_t id(const T &value) const { return indexes.at(value); }
inline const T at(size_t i) const { return values[i]; }
};
// FenwicTree {{{
/**
* @brief Fenwic-Tree (Binary-Indexed-Tree)
*/
template <class T>
class FenwicTree {
size_t m_size;
std::vector<T> dat;
public:
FenwicTree() = default;
explicit FenwicTree(size_t n)
: m_size(n)
, dat(n + 1) {}
//! i: [0, n)
void add(size_t i, const T& value) {
assert(i < m_size);
++i;
while (i <= m_size) dat[i] += value, i += i & -i;
}
//! [0, r)
const T prefixSum(size_t r) const {
T acc = 0;
while (r > 0) acc += dat[r], r -= r & -r;
return acc;
}
//! [l, r)
const T sum(size_t l, size_t r) const { return prefixSum(r) - prefixSum(l); }
//! i: [0, n)
const T at(size_t i) const { return prefixSum(i + 1) - prefixSum(i); }
//! return s.t. prefixSum(i) >= value
size_t lowerBound(T value) const {
if (value <= 0) return 0;
static const auto B = floorPow2(m_size);
size_t i = 0;
for (size_t k = B; k > 0; k >>= 1) {
if (i + k <= m_size && dat[i + k] < value) {
value -= dat[i + k];
i += k;
}
}
return i + 1;
}
private:
static inline constexpr size_t floorPow2(size_t x) noexcept {
size_t ret = 1;
while (ret <= x) ret <<= 1;
return ret >> 1;
}
};
// }}}
template <typename Key, typename Val>
struct FenwicTreeWithCompressor {
Compressor<Key> c;
FenwicTree<Val> ft;
FenwicTreeWithCompressor() = default;
explicit FenwicTreeWithCompressor(const Compressor<Key> &c_)
: c(c_)
, ft(c.size())
{}
inline void add(const Key &i, const Val &val) { ft.add(c.id(i), val); }
//! retuns i s.t. sum[0, i] >= value
const Key lower_bound(const Val &value) const {
return c.at(ft.lowerBound(value) - 1);
}
};
using namespace std;
using P = pair<long long, int>;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3f;
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int N, M, Q, K;
cin >> N >> M >> Q >> K;
static int C[100010];
rep(i, 0, N) cin >> C[i];
vector<P> G[100010];
rep(i, 0, M) {
int u, v, l;
cin >> u >> v >> l;
--u, --v;
G[u].emplace_back(l, v);
G[v].emplace_back(l, u);
}
priority_queue<P, vector<P>, greater<P>> pq;
long long dist[100010];
memset(dist, 0x3f, sizeof(dist));
pq.emplace(0, 0);
dist[0] = 0;
while (pq.size()) {
const auto [cur_cost, cur_node] = pq.top();
pq.pop();
if (dist[cur_node] < cur_cost) continue;
for (const auto &[cost, v]: G[cur_node]) {
if (chmin(dist[v], cur_cost + cost)) {
pq.emplace(cur_cost + cost, v);
}
}
}
Compressor<long long> zdist(dist, dist + N);
zdist.insert(LINF);
zdist.build();
FenwicTreeWithCompressor<long long, int> kind_num(zdist);
static multiset<long long> dists[100010];
rep(v, 0, N) {
dists[C[v]].insert(dist[v]);
}
rep(color, 0, 100010) {
dists[color].insert(LINF);
kind_num.add(*begin(dists[color]), 1);
}
while (Q--) {
int v, new_color;
cin >> v >> new_color;
--v;
if (new_color != C[v]) {
const int old_color = C[v];
C[v] = new_color;
kind_num.add(*begin(dists[old_color]), -1);
kind_num.add(*begin(dists[new_color]), -1);
dists[old_color].erase(dists[old_color].find(dist[v]));
dists[new_color].insert(dist[v]);
kind_num.add(*begin(dists[old_color]), +1);
kind_num.add(*begin(dists[new_color]), +1);
}
const auto ans = kind_num.lower_bound(K);
cout << (ans >= LINF ? -1 : ans) << "\n";
}
return 0;
}

ステータス

項目 データ
問題 1512 - Colorful Graph
ユーザー名 syoribu
投稿日時 2021-05-15 16:36:13
言語 C++17
状態 Accepted
得点 5
ソースコード長 5091 Byte
最大実行時間 248 ms
最大メモリ使用量 45424 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 148 ms 27868 KB
1
in02.txt AC 76 ms 18212 KB
1
in03.txt AC 101 ms 20564 KB
1
in04.txt AC 124 ms 23700 KB
1
in05.txt AC 79 ms 19096 KB
1
in06.txt AC 239 ms 36920 KB
1
in07.txt AC 233 ms 38120 KB
1
in08.txt AC 248 ms 39184 KB
1
in09.txt AC 229 ms 39484 KB
1
in10.txt AC 231 ms 39744 KB
1
in11.txt AC 115 ms 39520 KB
1
in12.txt AC 117 ms 39776 KB
1
in13.txt AC 89 ms 32216 KB
1
in14.txt AC 121 ms 27060 KB
1
in15.txt AC 89 ms 29060 KB
1
in16.txt AC 128 ms 33948 KB
1
in17.txt AC 234 ms 44332 KB
1
in18.txt AC 220 ms 44816 KB
1
in19.txt AC 237 ms 45424 KB
1
in20.txt AC 78 ms 27100 KB
1
in21.txt AC 82 ms 29400 KB
1
in22.txt AC 87 ms 30472 KB
1
in23.txt AC 71 ms 29068 KB
1
in24.txt AC 68 ms 29128 KB
1
in25.txt AC 73 ms 32560 KB
1
in26.txt AC 77 ms 33372 KB
1
in27.txt AC 56 ms 30724 KB
1
in28.txt AC 67 ms 30968 KB
1
sample01.txt AC 33 ms 30964 KB
1
sample02.txt AC 28 ms 30964 KB
1