Submission #66717

ソースコード

?
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
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
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);
}
}
}
int siz = 0;
map<long long, int> vtoi;
vector<long long> itov;
for(int i = 0; i < n; ++i){
vtoi[dist[i]];
}
vtoi[INF];
for(auto &&[key, value] : vtoi){
value = siz;
itov.emplace_back(key);
++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 15:52:45
言語 C++17
状態 Accepted
得点 5
ソースコード長 3902 Byte
最大実行時間 349 ms
最大メモリ使用量 41296 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in01.txt AC 170 ms 23124 KB
1
in02.txt AC 76 ms 13144 KB
1
in03.txt AC 103 ms 15808 KB
1
in04.txt AC 151 ms 18660 KB
1
in05.txt AC 88 ms 14408 KB
1
in06.txt AC 294 ms 32828 KB
1
in07.txt AC 284 ms 33836 KB
1
in08.txt AC 305 ms 34952 KB
1
in09.txt AC 306 ms 35312 KB
1
in10.txt AC 280 ms 35628 KB
1
in11.txt AC 160 ms 35200 KB
1
in12.txt AC 163 ms 35420 KB
1
in13.txt AC 92 ms 30516 KB
1
in14.txt AC 146 ms 23276 KB
1
in15.txt AC 91 ms 25512 KB
1
in16.txt AC 128 ms 32252 KB
1
in17.txt AC 289 ms 40740 KB
1
in18.txt AC 349 ms 41296 KB
1
in19.txt AC 281 ms 41092 KB
1
in20.txt AC 78 ms 23112 KB
1
in21.txt AC 89 ms 24600 KB
1
in22.txt AC 96 ms 25660 KB
1
in23.txt AC 75 ms 25356 KB
1
in24.txt AC 65 ms 25716 KB
1
in25.txt AC 77 ms 27828 KB
1
in26.txt AC 79 ms 28928 KB
1
in27.txt AC 54 ms 27608 KB
1
in28.txt AC 57 ms 27776 KB
1
sample01.txt AC 25 ms 27820 KB
1
sample02.txt AC 34 ms 27868 KB
1