Submission #66705

ソースコード

?
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) << endl;
}
return 0;
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 243 ms 27872 KB
1
in02.txt AC 161 ms 18224 KB
1
in03.txt AC 233 ms 20320 KB
1
in04.txt AC 283 ms 23448 KB
1
in05.txt AC 202 ms 18980 KB
1
in06.txt AC 417 ms 36808 KB
1
in07.txt AC 413 ms 37884 KB
1
in08.txt AC 414 ms 39080 KB
1
in09.txt AC 438 ms 39380 KB
1
in10.txt AC 418 ms 39648 KB
1
in11.txt AC 289 ms 39556 KB
1
in12.txt AC 289 ms 39812 KB
1
in13.txt AC 267 ms 32764 KB
1
in14.txt AC 292 ms 27124 KB
1
in15.txt AC 262 ms 29120 KB
1
in16.txt AC 302 ms 33884 KB
1
in17.txt AC 414 ms 44280 KB
1
in18.txt AC 401 ms 44768 KB
1
in19.txt AC 420 ms 45248 KB
1
in20.txt AC 248 ms 26932 KB
1
in21.txt AC 260 ms 29360 KB
1
in22.txt AC 261 ms 30432 KB
1
in23.txt AC 247 ms 29032 KB
1
in24.txt AC 246 ms 29092 KB
1
in25.txt AC 243 ms 32528 KB
1
in26.txt AC 258 ms 33212 KB
1
in27.txt AC 232 ms 30576 KB
1
in28.txt AC 236 ms 30828 KB
1
sample01.txt AC 30 ms 30820 KB
1
sample02.txt AC 31 ms 30820 KB
1