Submission #66689

ソースコード

?
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<map<long long, int> > cnt(1e5);
for(int i = 0; i < n; ++i){
cnt[c[i]][vtoi[dist[i]]]++;
}
for(int i = 0; i < 1e5; ++i){
if(!cnt[i].empty()){
BIT.add(cnt[i].begin()->first, 1);
}
}
for(int i = 0; i < q; ++i){
int x, nc;
cin >> x >> nc;
--x, --nc;
if(!cnt[c[x]].empty()){
BIT.add(cnt[c[x]].begin()->first, -1);
}
if(--cnt[c[x]][vtoi[dist[x]]] == 0){
cnt[c[x]].erase(vtoi[dist[x]]);
}
if(!cnt[c[x]].empty()){
BIT.add(cnt[c[x]].begin()->first, 1);
}
c[x] = nc;
if(!cnt[c[x]].empty()){
BIT.add(cnt[c[x]].begin()->first, -1);
}
cnt[c[x]][vtoi[dist[x]]]++;
if(!cnt[c[x]].empty()){
BIT.add(cnt[c[x]].begin()->first, 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-14 22:43:38
言語 C++17
状態 Accepted
得点 5
ソースコード長 3930 Byte
最大実行時間 304 ms
最大メモリ使用量 38088 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 163 ms 19412 KB
1
in02.txt AC 78 ms 8512 KB
1
in03.txt AC 102 ms 11452 KB
1
in04.txt AC 146 ms 14764 KB
1
in05.txt AC 83 ms 9772 KB
1
in06.txt AC 274 ms 29616 KB
1
in07.txt AC 279 ms 30672 KB
1
in08.txt AC 298 ms 31844 KB
1
in09.txt AC 282 ms 32252 KB
1
in10.txt AC 273 ms 32488 KB
1
in11.txt AC 153 ms 31864 KB
1
in12.txt AC 151 ms 32384 KB
1
in13.txt AC 82 ms 27532 KB
1
in14.txt AC 134 ms 19060 KB
1
in15.txt AC 73 ms 21748 KB
1
in16.txt AC 107 ms 29320 KB
1
in17.txt AC 266 ms 37736 KB
1
in18.txt AC 304 ms 38088 KB
1
in19.txt AC 282 ms 37936 KB
1
in20.txt AC 71 ms 18484 KB
1
in21.txt AC 75 ms 20132 KB
1
in22.txt AC 81 ms 21160 KB
1
in23.txt AC 64 ms 20648 KB
1
in24.txt AC 63 ms 21040 KB
1
in25.txt AC 72 ms 23476 KB
1
in26.txt AC 68 ms 24164 KB
1
in27.txt AC 47 ms 22832 KB
1
in28.txt AC 44 ms 23084 KB
1
sample01.txt AC 20 ms 23076 KB
1
sample02.txt AC 19 ms 23068 KB
1