Submission #66700

ソースコード

?
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
#include <bits/extc++.h>
using namespace std;
template< typename T >
struct BinaryIndexedTree {
private:
vector< T > data;
public:
BinaryIndexedTree() = default;
explicit BinaryIndexedTree(size_t sz) : data(sz + 1, 0) {}
explicit BinaryIndexedTree(const vector< T > &vs) : data(vs.size() + 1, 0) {
for(size_t i = 0; i < vs.size(); i++) data[i + 1] = vs[i];
for(size_t i = 1; i < data.size(); i++) {
size_t j = i + (i & -i);
if(j < data.size()) data[j] += data[i];
}
}
void add(int k, const T &x) {
for(++k; k < (int) data.size(); k += k & -k) data[k] += x;
}
T fold(int r) const {
T ret = T();
for(; r > 0; r -= r & -r) ret += data[r];
return ret;
}
T fold(int l, int r) const {
return fold(r) - fold(l);
}
int lower_bound(T x) const {
int i = 0;
for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) {
if(i + k < data.size() && data[i + k] < x) {
x -= data[i + k];
i += k;
}
}
return i;
}
int upper_bound(T x) const {
int i = 0;
for(int k = 1 << (__lg(data.size() - 1) + 1); k > 0; k >>= 1) {
if(i + k < data.size() && data[i + k] <= x) {
x -= data[i + k];
i += k;
}
}
return i;
}
};
int main(){
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
int n, m, q, k;
cin >> n >> m >> q >> k;
vector<int> c(n);
vector<vector<pair<int, int> > > graph(n);
for(int i = 0; i < n; ++i){
cin >> c[i];
--c[i];
}
for(int i = 0; i < m; ++i){
int u, v, l;
cin >> u >> v >> l;
--u, --v;
graph[u].emplace_back(v, l);
graph[v].emplace_back(u, l);
}
vector<long long> dist(n, LLONG_MAX >> 1);
priority_queue<pair<long long, int>, vector<pair<long long, int> >, greater<> > pq;
dist[0] = 0;
pq.emplace(0, 0);
while(!pq.empty()){
auto [cur_cost, cur_node] = pq.top();
pq.pop();
if(dist[cur_node] < cur_cost) continue;
for(auto [nxt_node, l] : graph[cur_node]){
if(dist[cur_node] + l < dist[nxt_node]){
dist[nxt_node] = dist[cur_node] + l;
pq.emplace(dist[nxt_node], nxt_node);
}
}
}
int idx = 0;
map<long long, int> vtoi;
vector<long long> itov;
for(int i = 0; i < n; ++i){
vtoi[dist[i]];
}
for(auto &&[key, value] : vtoi){
value = idx;
itov.emplace_back(key);
++idx;
}
int siz = idx;
BinaryIndexedTree<int> BIT(siz);
vector<multiset<long long> > dists(1e5);
for(int i = 0; i < n; ++i){
dists[c[i]].insert(vtoi[dist[i]]);
}
for(int i = 0; i < 1e5; ++i){
if(!dists[i].empty()){
BIT.add(*dists[i].begin(), 1);
}
}
for(int i = 0; i < q; ++i){
int x, nc;
cin >> x >> nc;
--x, --nc;
if(!dists[c[x]].empty()){
BIT.add(*dists[c[x]].begin(), -1);
}
if(dists[c[x]].find(vtoi[dist[x]]) != dists[c[x]].end()){
dists[c[x]].erase(dists[c[x]].find(vtoi[dist[x]]));
}
if(!dists[c[x]].empty()){
BIT.add(*dists[c[x]].begin(), 1);
}
c[x] = nc;
if(!dists[c[x]].empty()){
BIT.add(*dists[c[x]].begin(), -1);
}
dists[c[x]].insert(vtoi[dist[x]]);
if(!dists[c[x]].empty()){
BIT.add(*dists[c[x]].begin(), 1);
}
if(BIT.fold(siz) < k){
cout << -1 << '\n';
}else{
cout << itov[BIT.lower_bound(k)] << '\n';
}
}
return (0);
}

ステータス

項目 データ
問題 1512 - Colorful Graph
ユーザー名 ei1903
投稿日時 2021-05-15 07:42:58
言語 C++17
状態 Accepted
得点 5
ソースコード長 3977 Byte
最大実行時間 334 ms
最大メモリ使用量 36616 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 156 ms 18388 KB
1
in02.txt AC 68 ms 8492 KB
1
in03.txt AC 104 ms 11116 KB
1
in04.txt AC 134 ms 13912 KB
1
in05.txt AC 78 ms 9736 KB
1
in06.txt AC 290 ms 28244 KB
1
in07.txt AC 263 ms 29200 KB
1
in08.txt AC 267 ms 30400 KB
1
in09.txt AC 266 ms 30576 KB
1
in10.txt AC 274 ms 30844 KB
1
in11.txt AC 153 ms 30372 KB
1
in12.txt AC 156 ms 30668 KB
1
in13.txt AC 80 ms 25968 KB
1
in14.txt AC 117 ms 18804 KB
1
in15.txt AC 88 ms 20980 KB
1
in16.txt AC 175 ms 27668 KB
1
in17.txt AC 305 ms 36108 KB
1
in18.txt AC 334 ms 36616 KB
1
in19.txt AC 302 ms 36356 KB
1
in20.txt AC 74 ms 18464 KB
1
in21.txt AC 130 ms 20112 KB
1
in22.txt AC 85 ms 21148 KB
1
in23.txt AC 72 ms 20632 KB
1
in24.txt AC 63 ms 21152 KB
1
in25.txt AC 69 ms 23468 KB
1
in26.txt AC 74 ms 24288 KB
1
in27.txt AC 42 ms 22956 KB
1
in28.txt AC 37 ms 22952 KB
1
sample01.txt AC 23 ms 23076 KB
1
sample02.txt AC 20 ms 23200 KB
1