#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
const long long inf = (1LL << 61);
int n, m, k, q;
int startCities[maxn];
vector<pair<int, int>> g[maxn];
long long dist[maxn];
vector<long long> toTry;
struct Query
{
int from;
int to;
int idx;
Query()
{
}
Query(int _from, int _to, int _idx)
{
from = _from;
to = _to;
idx = _idx;
}
};
struct DSU
{
struct Roll
{
int *pos;
int val;
int t;
};
int par[maxn];
int dep[maxn];
stack<Roll> rollback;
void init()
{
while (!rollback.empty())
{
rollback.pop();
}
for (int i = 1; i <= n; ++i)
{
par[i] = i;
dep[i] = 1;
}
}
int root(int node)
{
if (node == par[node])
{
return node;
}
return root(par[node]);
}
void connect(int x, int y, int tim)
{
x = root(x);
y = root(y);
if (x == y)
{
return;
}
if (dep[x] < dep[y])
{
swap(x, y);
}
rollback.push({&par[y], par[y], tim});
par[y] = x;
if (dep[x] == dep[y])
{
rollback.push({&dep[x], dep[x], tim});
++dep[x];
}
}
void rollbackSmaller(int tim)
{
while (!rollback.empty() && tim >= rollback.top().t)
{
*rollback.top().pos = rollback.top().val;
rollback.pop();
}
}
inline bool areConnected(int x, int y)
{
return root(x) == root(y);
}
};
DSU dsu;
vector<Query> queries;
long long answers[maxn];
vector<pair<int, int>> byValue[maxn];
int PTR = 0;
void parallelBinarySearch(int l, int r, vector<int>& curr)
{
if (l > r)
{
return;
}
if (curr.empty())
{
return;
}
if (l == r)
{
for (int i = 0; i < curr.size(); ++i)
{
answers[queries[curr[i]].idx] = toTry[l];
}
return;
}
int mid = (l + r) / 2;
for (int i = PTR - 1; i >= mid + 1; --i)
{
for (int j = 0; j < byValue[i].size(); ++j)
{
dsu.connect(byValue[i][j].first, byValue[i][j].second, i);
}
}
PTR = mid + 1;
dsu.rollbackSmaller(mid);
vector<int> toLeft;
vector<int> toRight;
for (int i = 0; i < curr.size(); ++i)
{
if (dsu.areConnected(queries[curr[i]].from, queries[curr[i]].to) == true)
{
toRight.push_back(curr[i]);
}
else
{
toLeft.push_back(curr[i]);
}
}
curr.clear();
parallelBinarySearch(l, mid, toLeft);
parallelBinarySearch(mid + 1, r, toRight);
}
vector<long long> uniqueDistances()
{
set<long long> s;
vector<long long> res;
for (int i = 1; i <= n; ++i)
{
s.insert(dist[i]);
}
for (auto element : s)
{
res.push_back(element);
}
return res;
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> m;
for (int i = 1; i <= m; ++i)
{
int x, y, w;
cin >> x >> y >> w;
g[x].push_back(make_pair(y, w));
g[y].push_back(make_pair(x, w));
}
cin >> k;
for (int i = 1; i <= k; ++i)
{
cin >> startCities[i];
}
for (int i = 1; i <= n; ++i)
{
dist[i] = inf;
}
priority_queue<pair<long long, int>> pq;
for (int i = 1; i <= k; ++i)
{
pq.push(make_pair(0, startCities[i]));
dist[startCities[i]] = 0;
}
while (!pq.empty())
{
int node = pq.top().second;
long long curr = -pq.top().first;
pq.pop();
for (int i = 0; i < g[node].size(); ++i)
{
long long path = g[node][i].second + curr;
int to = g[node][i].first;
if (dist[to] > path)
{
dist[to] = path;
pq.push(make_pair(-path, to));
}
}
}
toTry = uniqueDistances();
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j < g[i].size(); ++j)
{
if (i < g[i][j].first)
{
long long d = min(dist[i], dist[g[i][j].first]);
int l = 0;
int r = toTry.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (toTry[mid] >= d)
{
r = mid - 1;
}
else
{
l = mid + 1;
}
}
byValue[l].push_back(make_pair(i, g[i][j].first));
}
}
}
cin >> q;
for (int i = 1; i <= q; ++i)
{
int from, to;
cin >> from >> to;
queries.push_back(Query(from, to, i - 1));
}
dsu.init();
vector<int> starting;
for (int i = 0; i < q; ++i)
{
starting.push_back(i);
}
if (clock() / CLOCKS_PER_SEC > 0.1)
{
return 1;
}
PTR = toTry.size();
parallelBinarySearch(0, PTR - 1, starting);
for (int i = 0; i < q; ++i)
{
cout << answers[i] << "\n";
}
return 0;
}
/*
9 12
1 9 4
1 2 5
2 3 7
2 4 3
4 3 6
3 6 4
8 7 10
6 7 5
5 8 1
9 5 7
5 4 12
6 8 2
2
4 7
5
1 6
5 3
4 8
5 8
1 5
*/
Compilation message
plan.cpp: In function 'void parallelBinarySearch(int, int, std::vector<int>&)':
plan.cpp:138:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for (int i = 0; i < curr.size(); ++i)
| ~~^~~~~~~~~~~~~
plan.cpp:150:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for (int j = 0; j < byValue[i].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~
plan.cpp:163:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
163 | for (int i = 0; i < curr.size(); ++i)
| ~~^~~~~~~~~~~~~
plan.cpp: In function 'int main()':
plan.cpp:247:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
247 | for (int i = 0; i < g[node].size(); ++i)
| ~~^~~~~~~~~~~~~~~~
plan.cpp:264:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
264 | for (int j = 0; j < g[i].size(); ++j)
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
7256 KB |
Output is correct |
2 |
Correct |
2 ms |
7516 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7256 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
7660 KB |
Output is correct |
7 |
Correct |
2 ms |
7516 KB |
Output is correct |
8 |
Correct |
2 ms |
7516 KB |
Output is correct |
9 |
Correct |
3 ms |
7516 KB |
Output is correct |
10 |
Correct |
2 ms |
7544 KB |
Output is correct |
11 |
Correct |
3 ms |
7516 KB |
Output is correct |
12 |
Correct |
2 ms |
7516 KB |
Output is correct |
13 |
Correct |
3 ms |
7516 KB |
Output is correct |
14 |
Correct |
3 ms |
7516 KB |
Output is correct |
15 |
Correct |
3 ms |
7516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
7256 KB |
Output is correct |
2 |
Correct |
2 ms |
7516 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7256 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
7660 KB |
Output is correct |
7 |
Correct |
2 ms |
7516 KB |
Output is correct |
8 |
Correct |
2 ms |
7516 KB |
Output is correct |
9 |
Correct |
3 ms |
7516 KB |
Output is correct |
10 |
Correct |
2 ms |
7544 KB |
Output is correct |
11 |
Correct |
3 ms |
7516 KB |
Output is correct |
12 |
Correct |
2 ms |
7516 KB |
Output is correct |
13 |
Correct |
3 ms |
7516 KB |
Output is correct |
14 |
Correct |
3 ms |
7516 KB |
Output is correct |
15 |
Correct |
3 ms |
7516 KB |
Output is correct |
16 |
Correct |
107 ms |
17220 KB |
Output is correct |
17 |
Correct |
341 ms |
34180 KB |
Output is correct |
18 |
Correct |
25 ms |
9884 KB |
Output is correct |
19 |
Correct |
77 ms |
22096 KB |
Output is correct |
20 |
Correct |
298 ms |
34464 KB |
Output is correct |
21 |
Correct |
167 ms |
23744 KB |
Output is correct |
22 |
Correct |
147 ms |
19544 KB |
Output is correct |
23 |
Correct |
317 ms |
40644 KB |
Output is correct |
24 |
Correct |
378 ms |
41332 KB |
Output is correct |
25 |
Correct |
306 ms |
40860 KB |
Output is correct |
26 |
Correct |
83 ms |
24444 KB |
Output is correct |
27 |
Correct |
78 ms |
24388 KB |
Output is correct |
28 |
Correct |
73 ms |
24364 KB |
Output is correct |
29 |
Correct |
80 ms |
24388 KB |
Output is correct |
30 |
Correct |
73 ms |
24636 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
7260 KB |
Output is correct |
2 |
Correct |
2 ms |
7260 KB |
Output is correct |
3 |
Correct |
2 ms |
7512 KB |
Output is correct |
4 |
Correct |
2 ms |
7516 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
7516 KB |
Output is correct |
7 |
Correct |
2 ms |
7260 KB |
Output is correct |
8 |
Correct |
2 ms |
7516 KB |
Output is correct |
9 |
Correct |
2 ms |
7260 KB |
Output is correct |
10 |
Correct |
2 ms |
7512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
108 ms |
18128 KB |
Output is correct |
2 |
Correct |
266 ms |
30512 KB |
Output is correct |
3 |
Correct |
286 ms |
30404 KB |
Output is correct |
4 |
Correct |
89 ms |
16336 KB |
Output is correct |
5 |
Correct |
247 ms |
30916 KB |
Output is correct |
6 |
Correct |
240 ms |
29552 KB |
Output is correct |
7 |
Correct |
259 ms |
30652 KB |
Output is correct |
8 |
Correct |
242 ms |
29640 KB |
Output is correct |
9 |
Correct |
268 ms |
29712 KB |
Output is correct |
10 |
Correct |
280 ms |
30736 KB |
Output is correct |
11 |
Correct |
275 ms |
30488 KB |
Output is correct |
12 |
Correct |
297 ms |
30912 KB |
Output is correct |
13 |
Correct |
265 ms |
30428 KB |
Output is correct |
14 |
Correct |
241 ms |
29908 KB |
Output is correct |
15 |
Correct |
273 ms |
30632 KB |
Output is correct |
16 |
Correct |
274 ms |
30296 KB |
Output is correct |
17 |
Correct |
280 ms |
29608 KB |
Output is correct |
18 |
Correct |
276 ms |
29744 KB |
Output is correct |
19 |
Correct |
82 ms |
16336 KB |
Output is correct |
20 |
Correct |
272 ms |
30364 KB |
Output is correct |
21 |
Correct |
215 ms |
29256 KB |
Output is correct |
22 |
Correct |
56 ms |
15420 KB |
Output is correct |
23 |
Correct |
86 ms |
15564 KB |
Output is correct |
24 |
Correct |
71 ms |
15420 KB |
Output is correct |
25 |
Correct |
48 ms |
15440 KB |
Output is correct |
26 |
Correct |
83 ms |
15056 KB |
Output is correct |
27 |
Correct |
76 ms |
16332 KB |
Output is correct |
28 |
Correct |
49 ms |
15164 KB |
Output is correct |
29 |
Correct |
90 ms |
16300 KB |
Output is correct |
30 |
Correct |
58 ms |
15424 KB |
Output is correct |
31 |
Correct |
81 ms |
16340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
7256 KB |
Output is correct |
2 |
Correct |
2 ms |
7516 KB |
Output is correct |
3 |
Correct |
2 ms |
7516 KB |
Output is correct |
4 |
Correct |
2 ms |
7256 KB |
Output is correct |
5 |
Correct |
2 ms |
7516 KB |
Output is correct |
6 |
Correct |
2 ms |
7660 KB |
Output is correct |
7 |
Correct |
2 ms |
7516 KB |
Output is correct |
8 |
Correct |
2 ms |
7516 KB |
Output is correct |
9 |
Correct |
3 ms |
7516 KB |
Output is correct |
10 |
Correct |
2 ms |
7544 KB |
Output is correct |
11 |
Correct |
3 ms |
7516 KB |
Output is correct |
12 |
Correct |
2 ms |
7516 KB |
Output is correct |
13 |
Correct |
3 ms |
7516 KB |
Output is correct |
14 |
Correct |
3 ms |
7516 KB |
Output is correct |
15 |
Correct |
3 ms |
7516 KB |
Output is correct |
16 |
Correct |
107 ms |
17220 KB |
Output is correct |
17 |
Correct |
341 ms |
34180 KB |
Output is correct |
18 |
Correct |
25 ms |
9884 KB |
Output is correct |
19 |
Correct |
77 ms |
22096 KB |
Output is correct |
20 |
Correct |
298 ms |
34464 KB |
Output is correct |
21 |
Correct |
167 ms |
23744 KB |
Output is correct |
22 |
Correct |
147 ms |
19544 KB |
Output is correct |
23 |
Correct |
317 ms |
40644 KB |
Output is correct |
24 |
Correct |
378 ms |
41332 KB |
Output is correct |
25 |
Correct |
306 ms |
40860 KB |
Output is correct |
26 |
Correct |
83 ms |
24444 KB |
Output is correct |
27 |
Correct |
78 ms |
24388 KB |
Output is correct |
28 |
Correct |
73 ms |
24364 KB |
Output is correct |
29 |
Correct |
80 ms |
24388 KB |
Output is correct |
30 |
Correct |
73 ms |
24636 KB |
Output is correct |
31 |
Correct |
2 ms |
7260 KB |
Output is correct |
32 |
Correct |
2 ms |
7260 KB |
Output is correct |
33 |
Correct |
2 ms |
7512 KB |
Output is correct |
34 |
Correct |
2 ms |
7516 KB |
Output is correct |
35 |
Correct |
2 ms |
7516 KB |
Output is correct |
36 |
Correct |
2 ms |
7516 KB |
Output is correct |
37 |
Correct |
2 ms |
7260 KB |
Output is correct |
38 |
Correct |
2 ms |
7516 KB |
Output is correct |
39 |
Correct |
2 ms |
7260 KB |
Output is correct |
40 |
Correct |
2 ms |
7512 KB |
Output is correct |
41 |
Correct |
108 ms |
18128 KB |
Output is correct |
42 |
Correct |
266 ms |
30512 KB |
Output is correct |
43 |
Correct |
286 ms |
30404 KB |
Output is correct |
44 |
Correct |
89 ms |
16336 KB |
Output is correct |
45 |
Correct |
247 ms |
30916 KB |
Output is correct |
46 |
Correct |
240 ms |
29552 KB |
Output is correct |
47 |
Correct |
259 ms |
30652 KB |
Output is correct |
48 |
Correct |
242 ms |
29640 KB |
Output is correct |
49 |
Correct |
268 ms |
29712 KB |
Output is correct |
50 |
Correct |
280 ms |
30736 KB |
Output is correct |
51 |
Correct |
275 ms |
30488 KB |
Output is correct |
52 |
Correct |
297 ms |
30912 KB |
Output is correct |
53 |
Correct |
265 ms |
30428 KB |
Output is correct |
54 |
Correct |
241 ms |
29908 KB |
Output is correct |
55 |
Correct |
273 ms |
30632 KB |
Output is correct |
56 |
Correct |
274 ms |
30296 KB |
Output is correct |
57 |
Correct |
280 ms |
29608 KB |
Output is correct |
58 |
Correct |
276 ms |
29744 KB |
Output is correct |
59 |
Correct |
82 ms |
16336 KB |
Output is correct |
60 |
Correct |
272 ms |
30364 KB |
Output is correct |
61 |
Correct |
215 ms |
29256 KB |
Output is correct |
62 |
Correct |
56 ms |
15420 KB |
Output is correct |
63 |
Correct |
86 ms |
15564 KB |
Output is correct |
64 |
Correct |
71 ms |
15420 KB |
Output is correct |
65 |
Correct |
48 ms |
15440 KB |
Output is correct |
66 |
Correct |
83 ms |
15056 KB |
Output is correct |
67 |
Correct |
76 ms |
16332 KB |
Output is correct |
68 |
Correct |
49 ms |
15164 KB |
Output is correct |
69 |
Correct |
90 ms |
16300 KB |
Output is correct |
70 |
Correct |
58 ms |
15424 KB |
Output is correct |
71 |
Correct |
81 ms |
16340 KB |
Output is correct |
72 |
Correct |
171 ms |
25840 KB |
Output is correct |
73 |
Correct |
349 ms |
41492 KB |
Output is correct |
74 |
Correct |
325 ms |
42028 KB |
Output is correct |
75 |
Correct |
369 ms |
42272 KB |
Output is correct |
76 |
Correct |
380 ms |
41640 KB |
Output is correct |
77 |
Correct |
318 ms |
41604 KB |
Output is correct |
78 |
Correct |
347 ms |
41532 KB |
Output is correct |
79 |
Correct |
334 ms |
42188 KB |
Output is correct |
80 |
Correct |
321 ms |
41920 KB |
Output is correct |
81 |
Correct |
366 ms |
41524 KB |
Output is correct |
82 |
Correct |
304 ms |
41928 KB |
Output is correct |
83 |
Correct |
358 ms |
41820 KB |
Output is correct |
84 |
Correct |
324 ms |
41312 KB |
Output is correct |
85 |
Correct |
328 ms |
42360 KB |
Output is correct |
86 |
Correct |
352 ms |
41856 KB |
Output is correct |
87 |
Correct |
375 ms |
42028 KB |
Output is correct |
88 |
Correct |
306 ms |
41664 KB |
Output is correct |
89 |
Correct |
172 ms |
22440 KB |
Output is correct |
90 |
Correct |
334 ms |
41644 KB |
Output is correct |
91 |
Correct |
278 ms |
42156 KB |
Output is correct |
92 |
Correct |
75 ms |
24640 KB |
Output is correct |
93 |
Correct |
175 ms |
22616 KB |
Output is correct |
94 |
Correct |
82 ms |
24364 KB |
Output is correct |
95 |
Correct |
75 ms |
24404 KB |
Output is correct |
96 |
Correct |
152 ms |
25372 KB |
Output is correct |
97 |
Correct |
158 ms |
24780 KB |
Output is correct |
98 |
Correct |
97 ms |
24496 KB |
Output is correct |
99 |
Correct |
156 ms |
24772 KB |
Output is correct |
100 |
Correct |
92 ms |
24644 KB |
Output is correct |