Submission #66718

ソースコード

?
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
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;
const long long INF = 1LL << 60;
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> color(n);
vector<vector<pair<int, int> > > graph(n);
for(int i = 0; i < n; ++i){
cin >> color[i];
--color[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, INF);
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);
}
}
}
auto sorted = dist;
sort(sorted.begin(), sorted.end());
sorted.emplace_back(INF);
int siz = 0;
unordered_map<long long, int> vtoi;
vector<long long> itov;
for(auto e : sorted){
vtoi[e] = siz;
itov.emplace_back(e);
++siz;
}
BinaryIndexedTree<int> BIT(siz);
vector<multiset<long long> > dists(1e5);
for(int i = 0; i < 1e5; ++i){
dists[i].insert(vtoi[INF]);
}
for(int i = 0; i < n; ++i){
dists[color[i]].insert(vtoi[dist[i]]);
}
for(int i = 0; i < 1e5; ++i){
BIT.add(*dists[i].begin(), 1);
}
for(int i = 0; i < q; ++i){
int x, c;
cin >> x >> c;
--x, --c;
BIT.add(*dists[color[x]].begin(), -1);
dists[color[x]].erase(dists[color[x]].find(vtoi[dist[x]]));
BIT.add(*dists[color[x]].begin(), 1);
color[x] = c;
BIT.add(*dists[color[x]].begin(), -1);
dists[color[x]].insert(vtoi[dist[x]]);
BIT.add(*dists[color[x]].begin(), 1);
long long ans = itov[BIT.lower_bound(k)];
if(ans == INF){
cout << -1 << '\n';
}else{
cout << ans << '\n';
}
}
return (0);
}

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 140 ms 22492 KB
1
in02.txt AC 68 ms 12960 KB
1
in03.txt AC 94 ms 15388 KB
1
in04.txt AC 116 ms 18212 KB
1
in05.txt AC 73 ms 14404 KB
1
in06.txt AC 240 ms 31440 KB
1
in07.txt AC 220 ms 32380 KB
1
in08.txt AC 228 ms 33564 KB
1
in09.txt AC 218 ms 34116 KB
1
in10.txt AC 226 ms 34248 KB
1
in11.txt AC 107 ms 33768 KB
1
in12.txt AC 103 ms 34052 KB
1
in13.txt AC 97 ms 32552 KB
1
in14.txt AC 110 ms 22900 KB
1
in15.txt AC 92 ms 26576 KB
1
in16.txt AC 138 ms 34252 KB
1
in17.txt AC 223 ms 39244 KB
1
in18.txt AC 231 ms 39748 KB
1
in19.txt AC 218 ms 39720 KB
1
in20.txt AC 81 ms 22968 KB
1
in21.txt AC 74 ms 24592 KB
1
in22.txt AC 83 ms 25660 KB
1
in23.txt AC 72 ms 25364 KB
1
in24.txt AC 61 ms 25848 KB
1
in25.txt AC 77 ms 27964 KB
1
in26.txt AC 73 ms 28820 KB
1
in27.txt AC 58 ms 27624 KB
1
in28.txt AC 57 ms 27800 KB
1
sample01.txt AC 38 ms 27844 KB
1
sample02.txt AC 26 ms 27896 KB
1