#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44
using namespace std;
const int INF = 1e9;
const int MAXN = (int) 1e5;
vector < pair <int, int> > g[MAXN + 1];
int bad[MAXN + 1];
int n, m, q;
bool inq[MAXN + 1];
int dist[MAXN + 1];
inline void BF(int k) {
queue <int> Q;
for(int i = 1; i <= n; i++) {
dist[i] = INF;
}
for(int i = 1; i <= k; i++) {
Q.push(bad[i]);
dist[bad[i]] = 0;
inq[bad[i]] = 1;
}
while(Q.size()) {
int nod = Q.front();
inq[nod] = 0;
Q.pop();
for(auto it : g[nod]) {
if(dist[it.first] > dist[nod] + it.second) {
dist[it.first] = dist[nod] + it.second;
if(!inq[it.first]) {
inq[it.first] = 1;
Q.push(it.first);
}
}
}
}
}
struct DSU {
vector <int> par;
inline void init(int n) {
par.resize(n + 1);
}
inline int myfind(int x) {
if(par[x] == 0)
return x;
return par[x] = myfind(par[x]);
}
inline void myunion(int x, int y) {
x = myfind(x), y = myfind(y);
if(x != y) {
par[x] = y;
}
}
};
struct Edge {
int x, y;
int cst;
bool operator <(const Edge &other) const {
return cst > other.cst;
}
};
vector <Edge> edges;
pair <int, int> res[MAXN + 1], qry[MAXN + 1];
int sol[MAXN + 1];
inline void solve(int step) {
DSU dsu;
dsu.init(n);
sort(res + 1, res + q + 1);
int pos = 0;
for(int i = q; i >= 1; i--) {
while(pos < m && edges[pos].cst >= res[i].first + step) {
dsu.myunion(edges[pos].x, edges[pos].y);
pos++;
}
if(dsu.myfind(qry[res[i].second].first) == dsu.myfind(qry[res[i].second].second)) {
res[i].first += step;
}
}
}
int main() {
//ifstream cin("A.in");
//ofstream cout("A.out");
int i, k;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(i = 1; i <= m; i++) {
int a, b, w;
cin >> a >> b >> w;
g[a].push_back({b, w});
g[b].push_back({a, w});
edges.push_back({a, b, 0});
}
cin >> k;
for(i = 1; i <= k; i++) {
cin >> bad[i];
}
BF(k);
for(i = 0; i < m; i++) {
edges[i].cst = min(dist[edges[i].x], dist[edges[i].y]);
}
sort(edges.begin(), edges.end());
cin >> q;
for(i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
qry[i] = {a, b};
res[i] = {0, i};
}
for(int step = 1 << 30; step; step >>= 1) {
solve(step);
}
for(i = 1; i <= q; i++) {
sol[res[i].second] = res[i].first;
}
for(i = 1; i <= q; i++) {
cout << sol[i] << "\n";
}
//cin.close();
//cout.close();
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2684 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
6 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
6 ms |
2808 KB |
Output is correct |
12 |
Correct |
5 ms |
2808 KB |
Output is correct |
13 |
Correct |
6 ms |
2808 KB |
Output is correct |
14 |
Correct |
6 ms |
2808 KB |
Output is correct |
15 |
Correct |
6 ms |
2808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2684 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
6 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
6 ms |
2808 KB |
Output is correct |
12 |
Correct |
5 ms |
2808 KB |
Output is correct |
13 |
Correct |
6 ms |
2808 KB |
Output is correct |
14 |
Correct |
6 ms |
2808 KB |
Output is correct |
15 |
Correct |
6 ms |
2808 KB |
Output is correct |
16 |
Correct |
353 ms |
10596 KB |
Output is correct |
17 |
Correct |
959 ms |
26068 KB |
Output is correct |
18 |
Correct |
65 ms |
4780 KB |
Output is correct |
19 |
Correct |
201 ms |
12360 KB |
Output is correct |
20 |
Correct |
948 ms |
25888 KB |
Output is correct |
21 |
Correct |
367 ms |
14764 KB |
Output is correct |
22 |
Correct |
306 ms |
11248 KB |
Output is correct |
23 |
Correct |
924 ms |
25884 KB |
Output is correct |
24 |
Correct |
909 ms |
25880 KB |
Output is correct |
25 |
Correct |
792 ms |
25752 KB |
Output is correct |
26 |
Correct |
183 ms |
11672 KB |
Output is correct |
27 |
Correct |
198 ms |
11676 KB |
Output is correct |
28 |
Correct |
192 ms |
11552 KB |
Output is correct |
29 |
Correct |
209 ms |
11992 KB |
Output is correct |
30 |
Correct |
197 ms |
12032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
4 ms |
2680 KB |
Output is correct |
3 |
Correct |
4 ms |
2680 KB |
Output is correct |
4 |
Correct |
4 ms |
2680 KB |
Output is correct |
5 |
Correct |
4 ms |
2680 KB |
Output is correct |
6 |
Correct |
4 ms |
2680 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
4 ms |
2680 KB |
Output is correct |
10 |
Correct |
4 ms |
2680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
231 ms |
12448 KB |
Output is correct |
2 |
Correct |
550 ms |
23464 KB |
Output is correct |
3 |
Correct |
557 ms |
23588 KB |
Output is correct |
4 |
Correct |
122 ms |
8828 KB |
Output is correct |
5 |
Correct |
678 ms |
23536 KB |
Output is correct |
6 |
Correct |
529 ms |
23564 KB |
Output is correct |
7 |
Correct |
552 ms |
23480 KB |
Output is correct |
8 |
Correct |
503 ms |
23536 KB |
Output is correct |
9 |
Correct |
531 ms |
23468 KB |
Output is correct |
10 |
Correct |
673 ms |
23520 KB |
Output is correct |
11 |
Correct |
711 ms |
23596 KB |
Output is correct |
12 |
Correct |
611 ms |
23564 KB |
Output is correct |
13 |
Correct |
608 ms |
23448 KB |
Output is correct |
14 |
Correct |
456 ms |
23636 KB |
Output is correct |
15 |
Correct |
562 ms |
23676 KB |
Output is correct |
16 |
Correct |
573 ms |
23524 KB |
Output is correct |
17 |
Correct |
503 ms |
23448 KB |
Output is correct |
18 |
Correct |
502 ms |
23636 KB |
Output is correct |
19 |
Correct |
68 ms |
8364 KB |
Output is correct |
20 |
Correct |
556 ms |
23448 KB |
Output is correct |
21 |
Correct |
389 ms |
23832 KB |
Output is correct |
22 |
Correct |
77 ms |
9244 KB |
Output is correct |
23 |
Correct |
122 ms |
8336 KB |
Output is correct |
24 |
Correct |
67 ms |
9996 KB |
Output is correct |
25 |
Correct |
73 ms |
9628 KB |
Output is correct |
26 |
Correct |
113 ms |
8364 KB |
Output is correct |
27 |
Correct |
123 ms |
8704 KB |
Output is correct |
28 |
Correct |
62 ms |
10140 KB |
Output is correct |
29 |
Correct |
125 ms |
8704 KB |
Output is correct |
30 |
Correct |
66 ms |
10012 KB |
Output is correct |
31 |
Correct |
124 ms |
8760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
2680 KB |
Output is correct |
2 |
Correct |
5 ms |
2808 KB |
Output is correct |
3 |
Correct |
5 ms |
2808 KB |
Output is correct |
4 |
Correct |
4 ms |
2684 KB |
Output is correct |
5 |
Correct |
5 ms |
2808 KB |
Output is correct |
6 |
Correct |
5 ms |
2808 KB |
Output is correct |
7 |
Correct |
4 ms |
2680 KB |
Output is correct |
8 |
Correct |
4 ms |
2680 KB |
Output is correct |
9 |
Correct |
6 ms |
2808 KB |
Output is correct |
10 |
Correct |
5 ms |
2808 KB |
Output is correct |
11 |
Correct |
6 ms |
2808 KB |
Output is correct |
12 |
Correct |
5 ms |
2808 KB |
Output is correct |
13 |
Correct |
6 ms |
2808 KB |
Output is correct |
14 |
Correct |
6 ms |
2808 KB |
Output is correct |
15 |
Correct |
6 ms |
2808 KB |
Output is correct |
16 |
Correct |
353 ms |
10596 KB |
Output is correct |
17 |
Correct |
959 ms |
26068 KB |
Output is correct |
18 |
Correct |
65 ms |
4780 KB |
Output is correct |
19 |
Correct |
201 ms |
12360 KB |
Output is correct |
20 |
Correct |
948 ms |
25888 KB |
Output is correct |
21 |
Correct |
367 ms |
14764 KB |
Output is correct |
22 |
Correct |
306 ms |
11248 KB |
Output is correct |
23 |
Correct |
924 ms |
25884 KB |
Output is correct |
24 |
Correct |
909 ms |
25880 KB |
Output is correct |
25 |
Correct |
792 ms |
25752 KB |
Output is correct |
26 |
Correct |
183 ms |
11672 KB |
Output is correct |
27 |
Correct |
198 ms |
11676 KB |
Output is correct |
28 |
Correct |
192 ms |
11552 KB |
Output is correct |
29 |
Correct |
209 ms |
11992 KB |
Output is correct |
30 |
Correct |
197 ms |
12032 KB |
Output is correct |
31 |
Correct |
4 ms |
2680 KB |
Output is correct |
32 |
Correct |
4 ms |
2680 KB |
Output is correct |
33 |
Correct |
4 ms |
2680 KB |
Output is correct |
34 |
Correct |
4 ms |
2680 KB |
Output is correct |
35 |
Correct |
4 ms |
2680 KB |
Output is correct |
36 |
Correct |
4 ms |
2680 KB |
Output is correct |
37 |
Correct |
4 ms |
2680 KB |
Output is correct |
38 |
Correct |
4 ms |
2680 KB |
Output is correct |
39 |
Correct |
4 ms |
2680 KB |
Output is correct |
40 |
Correct |
4 ms |
2680 KB |
Output is correct |
41 |
Correct |
231 ms |
12448 KB |
Output is correct |
42 |
Correct |
550 ms |
23464 KB |
Output is correct |
43 |
Correct |
557 ms |
23588 KB |
Output is correct |
44 |
Correct |
122 ms |
8828 KB |
Output is correct |
45 |
Correct |
678 ms |
23536 KB |
Output is correct |
46 |
Correct |
529 ms |
23564 KB |
Output is correct |
47 |
Correct |
552 ms |
23480 KB |
Output is correct |
48 |
Correct |
503 ms |
23536 KB |
Output is correct |
49 |
Correct |
531 ms |
23468 KB |
Output is correct |
50 |
Correct |
673 ms |
23520 KB |
Output is correct |
51 |
Correct |
711 ms |
23596 KB |
Output is correct |
52 |
Correct |
611 ms |
23564 KB |
Output is correct |
53 |
Correct |
608 ms |
23448 KB |
Output is correct |
54 |
Correct |
456 ms |
23636 KB |
Output is correct |
55 |
Correct |
562 ms |
23676 KB |
Output is correct |
56 |
Correct |
573 ms |
23524 KB |
Output is correct |
57 |
Correct |
503 ms |
23448 KB |
Output is correct |
58 |
Correct |
502 ms |
23636 KB |
Output is correct |
59 |
Correct |
68 ms |
8364 KB |
Output is correct |
60 |
Correct |
556 ms |
23448 KB |
Output is correct |
61 |
Correct |
389 ms |
23832 KB |
Output is correct |
62 |
Correct |
77 ms |
9244 KB |
Output is correct |
63 |
Correct |
122 ms |
8336 KB |
Output is correct |
64 |
Correct |
67 ms |
9996 KB |
Output is correct |
65 |
Correct |
73 ms |
9628 KB |
Output is correct |
66 |
Correct |
113 ms |
8364 KB |
Output is correct |
67 |
Correct |
123 ms |
8704 KB |
Output is correct |
68 |
Correct |
62 ms |
10140 KB |
Output is correct |
69 |
Correct |
125 ms |
8704 KB |
Output is correct |
70 |
Correct |
66 ms |
10012 KB |
Output is correct |
71 |
Correct |
124 ms |
8760 KB |
Output is correct |
72 |
Correct |
562 ms |
14968 KB |
Output is correct |
73 |
Correct |
928 ms |
25888 KB |
Output is correct |
74 |
Correct |
930 ms |
25872 KB |
Output is correct |
75 |
Correct |
915 ms |
26020 KB |
Output is correct |
76 |
Correct |
916 ms |
25944 KB |
Output is correct |
77 |
Correct |
911 ms |
25920 KB |
Output is correct |
78 |
Correct |
922 ms |
25896 KB |
Output is correct |
79 |
Correct |
899 ms |
25876 KB |
Output is correct |
80 |
Correct |
937 ms |
26020 KB |
Output is correct |
81 |
Correct |
908 ms |
26008 KB |
Output is correct |
82 |
Correct |
874 ms |
25920 KB |
Output is correct |
83 |
Correct |
862 ms |
25880 KB |
Output is correct |
84 |
Correct |
837 ms |
25836 KB |
Output is correct |
85 |
Correct |
788 ms |
25780 KB |
Output is correct |
86 |
Correct |
851 ms |
25948 KB |
Output is correct |
87 |
Correct |
896 ms |
26008 KB |
Output is correct |
88 |
Correct |
939 ms |
25888 KB |
Output is correct |
89 |
Correct |
507 ms |
11432 KB |
Output is correct |
90 |
Correct |
930 ms |
25840 KB |
Output is correct |
91 |
Correct |
566 ms |
26000 KB |
Output is correct |
92 |
Correct |
203 ms |
12188 KB |
Output is correct |
93 |
Correct |
426 ms |
11100 KB |
Output is correct |
94 |
Correct |
185 ms |
11852 KB |
Output is correct |
95 |
Correct |
195 ms |
12060 KB |
Output is correct |
96 |
Correct |
397 ms |
10604 KB |
Output is correct |
97 |
Correct |
400 ms |
10792 KB |
Output is correct |
98 |
Correct |
193 ms |
12060 KB |
Output is correct |
99 |
Correct |
423 ms |
10772 KB |
Output is correct |
100 |
Correct |
214 ms |
11848 KB |
Output is correct |