#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn = 100100;
class dsu {
public:
int uparent[maxn], n;
int usize[maxn];
void init(int _n) {
n = _n;
for(int i=0;i<=n;i++) {
uparent[i] = i;
usize[i] = 1;
}
}
int ufind(int x) {
while(x != uparent[x])
x = uparent[x];
return x;
}
void unite(int x, int y) {
x = ufind(x);
y = ufind(y);
if(x == y) return;
if(usize[x] > usize[y]) {
uparent[y] = x;
usize[x] += usize[y];
}
else {
uparent[x] = y;
usize[y] += usize[x];
}
}
}D;
int n, m, k, q, sz;
int result[maxn];
int dist[maxn];
bool visited[maxn];
vector<int>v; // NPP indexes
vector<pair<int,int> > g[maxn];
void get_distances() {
for(int i=0;i<=n;i++) {
visited[i] = false;
dist[i] = INT_MAX;
}
priority_queue<pii, vector<pii>, greater<pii> > pq;
for(int i:v) {
dist[i] = 0;
pq.push(mp(0, i));
}
while(!pq.empty()) {
int node = pq.top().second;
int curr = pq.top().first;
pq.pop();
if(visited[node]) continue;
visited[node] = true;
for(auto i:g[node]) {
if(!visited[i.first] && dist[i.first] > curr + i.second) {
dist[i.first] = curr + i.second;
pq.push(mp(dist[i.first], i.first));
}
}
}
}
int orgval[maxn];
vector<int>indexes[maxn];
map<int, int>cind;
set<int>st;
void preprocess() {
for(int i=1;i<=n;i++) {
st.insert(dist[i]);
}
int br = 0;
for(int i:st) {
cind[i] = br;
orgval[br] = i;
br++;
}
sz = br;
for(int i=1;i<=n;i++) {
indexes[cind[dist[i]]].pb(i);
}
}
int ql[maxn], qr[maxn];
int qs[maxn], qt[maxn];
bool answ[maxn];
int main() {
cin>>n>>m;
int a, b, c;
for(int i=0;i<m;i++) {
cin>>a>>b>>c;
g[a].pb(mp(b, c));
g[b].pb(mp(a, c));
}
int x;
cin>>k;
for(int i=0;i<k;i++) {
cin>>x;
v.pb(x);
}
get_distances();
preprocess();
cin>>q;
for(int i=1;i<=q;i++) {
cin>>qs[i]>>qt[i];
ql[i] = -1, qr[i] = sz;
}
for(int d=0;d<20;d++) {
//cout<<"At level: "<<d<<"\n";
D.init(n);
vector<int>qrs[maxn];
memset(answ,false,sizeof(answ));
//cout<<"Queries at beginning\n";
for(int i=1;i<=q;i++) {
int mid = (ql[i] + qr[i]) / 2;
if(qr[i] - ql[i] <= 1) {
result[i] = orgval[ql[i]];
continue;
}
qrs[mid].pb(i);
}
for(int j=sz-1;j>=0;j--) {
for(int i:indexes[j]) {
for(auto nxt:g[i]) {
if(dist[i] <= dist[nxt.first]) {
D.unite(i, nxt.first);
}
}
}
for(int i:qrs[j]) {
if(D.ufind(qs[i]) == D.ufind(qt[i])) {
answ[i] = true;
}
}
}
for(int i=1;i<=q;i++) {
if(qr[i] - ql[i] <= 1) continue;
int mid = (ql[i] + qr[i]) / 2;
if(answ[i]) {
ql[i] = mid;
}
else {
qr[i] = mid;
}
}
}
for(int i=1;i<=q;i++) {
cout<<result[i]<<"\n";
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
7552 KB |
Output is correct |
2 |
Correct |
15 ms |
7680 KB |
Output is correct |
3 |
Correct |
15 ms |
7680 KB |
Output is correct |
4 |
Correct |
13 ms |
7552 KB |
Output is correct |
5 |
Correct |
15 ms |
7680 KB |
Output is correct |
6 |
Correct |
15 ms |
7680 KB |
Output is correct |
7 |
Correct |
13 ms |
7552 KB |
Output is correct |
8 |
Correct |
13 ms |
7552 KB |
Output is correct |
9 |
Correct |
16 ms |
7680 KB |
Output is correct |
10 |
Correct |
18 ms |
7680 KB |
Output is correct |
11 |
Correct |
16 ms |
7680 KB |
Output is correct |
12 |
Correct |
15 ms |
7680 KB |
Output is correct |
13 |
Correct |
16 ms |
7680 KB |
Output is correct |
14 |
Correct |
17 ms |
7808 KB |
Output is correct |
15 |
Correct |
16 ms |
7808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
7552 KB |
Output is correct |
2 |
Correct |
15 ms |
7680 KB |
Output is correct |
3 |
Correct |
15 ms |
7680 KB |
Output is correct |
4 |
Correct |
13 ms |
7552 KB |
Output is correct |
5 |
Correct |
15 ms |
7680 KB |
Output is correct |
6 |
Correct |
15 ms |
7680 KB |
Output is correct |
7 |
Correct |
13 ms |
7552 KB |
Output is correct |
8 |
Correct |
13 ms |
7552 KB |
Output is correct |
9 |
Correct |
16 ms |
7680 KB |
Output is correct |
10 |
Correct |
18 ms |
7680 KB |
Output is correct |
11 |
Correct |
16 ms |
7680 KB |
Output is correct |
12 |
Correct |
15 ms |
7680 KB |
Output is correct |
13 |
Correct |
16 ms |
7680 KB |
Output is correct |
14 |
Correct |
17 ms |
7808 KB |
Output is correct |
15 |
Correct |
16 ms |
7808 KB |
Output is correct |
16 |
Correct |
563 ms |
19264 KB |
Output is correct |
17 |
Correct |
1610 ms |
36116 KB |
Output is correct |
18 |
Correct |
119 ms |
10284 KB |
Output is correct |
19 |
Correct |
383 ms |
19540 KB |
Output is correct |
20 |
Correct |
1597 ms |
36104 KB |
Output is correct |
21 |
Correct |
767 ms |
23876 KB |
Output is correct |
22 |
Correct |
781 ms |
31712 KB |
Output is correct |
23 |
Correct |
1584 ms |
35968 KB |
Output is correct |
24 |
Correct |
1538 ms |
35980 KB |
Output is correct |
25 |
Correct |
1550 ms |
36060 KB |
Output is correct |
26 |
Correct |
372 ms |
19296 KB |
Output is correct |
27 |
Correct |
383 ms |
19432 KB |
Output is correct |
28 |
Correct |
361 ms |
19288 KB |
Output is correct |
29 |
Correct |
379 ms |
19484 KB |
Output is correct |
30 |
Correct |
375 ms |
19676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
7552 KB |
Output is correct |
2 |
Correct |
12 ms |
7552 KB |
Output is correct |
3 |
Correct |
12 ms |
7552 KB |
Output is correct |
4 |
Correct |
12 ms |
7552 KB |
Output is correct |
5 |
Correct |
13 ms |
7552 KB |
Output is correct |
6 |
Correct |
13 ms |
7552 KB |
Output is correct |
7 |
Correct |
12 ms |
7552 KB |
Output is correct |
8 |
Correct |
13 ms |
7552 KB |
Output is correct |
9 |
Correct |
12 ms |
7552 KB |
Output is correct |
10 |
Correct |
13 ms |
7600 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
713 ms |
19380 KB |
Output is correct |
2 |
Correct |
1402 ms |
31616 KB |
Output is correct |
3 |
Correct |
1404 ms |
31764 KB |
Output is correct |
4 |
Correct |
577 ms |
26496 KB |
Output is correct |
5 |
Correct |
1395 ms |
31512 KB |
Output is correct |
6 |
Correct |
1376 ms |
31528 KB |
Output is correct |
7 |
Correct |
1413 ms |
31604 KB |
Output is correct |
8 |
Correct |
1408 ms |
31648 KB |
Output is correct |
9 |
Correct |
1398 ms |
31624 KB |
Output is correct |
10 |
Correct |
1454 ms |
31608 KB |
Output is correct |
11 |
Correct |
1438 ms |
31492 KB |
Output is correct |
12 |
Correct |
1464 ms |
31548 KB |
Output is correct |
13 |
Correct |
1376 ms |
31544 KB |
Output is correct |
14 |
Correct |
1405 ms |
31732 KB |
Output is correct |
15 |
Correct |
1366 ms |
31768 KB |
Output is correct |
16 |
Correct |
1420 ms |
31636 KB |
Output is correct |
17 |
Correct |
1384 ms |
31744 KB |
Output is correct |
18 |
Correct |
1391 ms |
31588 KB |
Output is correct |
19 |
Correct |
597 ms |
26504 KB |
Output is correct |
20 |
Correct |
1401 ms |
31420 KB |
Output is correct |
21 |
Correct |
1265 ms |
32556 KB |
Output is correct |
22 |
Correct |
314 ms |
15064 KB |
Output is correct |
23 |
Correct |
563 ms |
22492 KB |
Output is correct |
24 |
Correct |
242 ms |
15080 KB |
Output is correct |
25 |
Correct |
243 ms |
14940 KB |
Output is correct |
26 |
Correct |
436 ms |
18060 KB |
Output is correct |
27 |
Correct |
608 ms |
26500 KB |
Output is correct |
28 |
Correct |
276 ms |
15064 KB |
Output is correct |
29 |
Correct |
592 ms |
26616 KB |
Output is correct |
30 |
Correct |
243 ms |
15068 KB |
Output is correct |
31 |
Correct |
670 ms |
26604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
7552 KB |
Output is correct |
2 |
Correct |
15 ms |
7680 KB |
Output is correct |
3 |
Correct |
15 ms |
7680 KB |
Output is correct |
4 |
Correct |
13 ms |
7552 KB |
Output is correct |
5 |
Correct |
15 ms |
7680 KB |
Output is correct |
6 |
Correct |
15 ms |
7680 KB |
Output is correct |
7 |
Correct |
13 ms |
7552 KB |
Output is correct |
8 |
Correct |
13 ms |
7552 KB |
Output is correct |
9 |
Correct |
16 ms |
7680 KB |
Output is correct |
10 |
Correct |
18 ms |
7680 KB |
Output is correct |
11 |
Correct |
16 ms |
7680 KB |
Output is correct |
12 |
Correct |
15 ms |
7680 KB |
Output is correct |
13 |
Correct |
16 ms |
7680 KB |
Output is correct |
14 |
Correct |
17 ms |
7808 KB |
Output is correct |
15 |
Correct |
16 ms |
7808 KB |
Output is correct |
16 |
Correct |
563 ms |
19264 KB |
Output is correct |
17 |
Correct |
1610 ms |
36116 KB |
Output is correct |
18 |
Correct |
119 ms |
10284 KB |
Output is correct |
19 |
Correct |
383 ms |
19540 KB |
Output is correct |
20 |
Correct |
1597 ms |
36104 KB |
Output is correct |
21 |
Correct |
767 ms |
23876 KB |
Output is correct |
22 |
Correct |
781 ms |
31712 KB |
Output is correct |
23 |
Correct |
1584 ms |
35968 KB |
Output is correct |
24 |
Correct |
1538 ms |
35980 KB |
Output is correct |
25 |
Correct |
1550 ms |
36060 KB |
Output is correct |
26 |
Correct |
372 ms |
19296 KB |
Output is correct |
27 |
Correct |
383 ms |
19432 KB |
Output is correct |
28 |
Correct |
361 ms |
19288 KB |
Output is correct |
29 |
Correct |
379 ms |
19484 KB |
Output is correct |
30 |
Correct |
375 ms |
19676 KB |
Output is correct |
31 |
Correct |
12 ms |
7552 KB |
Output is correct |
32 |
Correct |
12 ms |
7552 KB |
Output is correct |
33 |
Correct |
12 ms |
7552 KB |
Output is correct |
34 |
Correct |
12 ms |
7552 KB |
Output is correct |
35 |
Correct |
13 ms |
7552 KB |
Output is correct |
36 |
Correct |
13 ms |
7552 KB |
Output is correct |
37 |
Correct |
12 ms |
7552 KB |
Output is correct |
38 |
Correct |
13 ms |
7552 KB |
Output is correct |
39 |
Correct |
12 ms |
7552 KB |
Output is correct |
40 |
Correct |
13 ms |
7600 KB |
Output is correct |
41 |
Correct |
713 ms |
19380 KB |
Output is correct |
42 |
Correct |
1402 ms |
31616 KB |
Output is correct |
43 |
Correct |
1404 ms |
31764 KB |
Output is correct |
44 |
Correct |
577 ms |
26496 KB |
Output is correct |
45 |
Correct |
1395 ms |
31512 KB |
Output is correct |
46 |
Correct |
1376 ms |
31528 KB |
Output is correct |
47 |
Correct |
1413 ms |
31604 KB |
Output is correct |
48 |
Correct |
1408 ms |
31648 KB |
Output is correct |
49 |
Correct |
1398 ms |
31624 KB |
Output is correct |
50 |
Correct |
1454 ms |
31608 KB |
Output is correct |
51 |
Correct |
1438 ms |
31492 KB |
Output is correct |
52 |
Correct |
1464 ms |
31548 KB |
Output is correct |
53 |
Correct |
1376 ms |
31544 KB |
Output is correct |
54 |
Correct |
1405 ms |
31732 KB |
Output is correct |
55 |
Correct |
1366 ms |
31768 KB |
Output is correct |
56 |
Correct |
1420 ms |
31636 KB |
Output is correct |
57 |
Correct |
1384 ms |
31744 KB |
Output is correct |
58 |
Correct |
1391 ms |
31588 KB |
Output is correct |
59 |
Correct |
597 ms |
26504 KB |
Output is correct |
60 |
Correct |
1401 ms |
31420 KB |
Output is correct |
61 |
Correct |
1265 ms |
32556 KB |
Output is correct |
62 |
Correct |
314 ms |
15064 KB |
Output is correct |
63 |
Correct |
563 ms |
22492 KB |
Output is correct |
64 |
Correct |
242 ms |
15080 KB |
Output is correct |
65 |
Correct |
243 ms |
14940 KB |
Output is correct |
66 |
Correct |
436 ms |
18060 KB |
Output is correct |
67 |
Correct |
608 ms |
26500 KB |
Output is correct |
68 |
Correct |
276 ms |
15064 KB |
Output is correct |
69 |
Correct |
592 ms |
26616 KB |
Output is correct |
70 |
Correct |
243 ms |
15068 KB |
Output is correct |
71 |
Correct |
670 ms |
26604 KB |
Output is correct |
72 |
Correct |
884 ms |
23608 KB |
Output is correct |
73 |
Correct |
1568 ms |
36236 KB |
Output is correct |
74 |
Correct |
1588 ms |
36016 KB |
Output is correct |
75 |
Correct |
1543 ms |
35976 KB |
Output is correct |
76 |
Correct |
1531 ms |
35968 KB |
Output is correct |
77 |
Correct |
1567 ms |
35968 KB |
Output is correct |
78 |
Correct |
1591 ms |
35960 KB |
Output is correct |
79 |
Correct |
1532 ms |
36124 KB |
Output is correct |
80 |
Correct |
1560 ms |
36124 KB |
Output is correct |
81 |
Correct |
1613 ms |
36036 KB |
Output is correct |
82 |
Correct |
1498 ms |
35924 KB |
Output is correct |
83 |
Correct |
1514 ms |
36200 KB |
Output is correct |
84 |
Correct |
1555 ms |
36112 KB |
Output is correct |
85 |
Correct |
1520 ms |
36008 KB |
Output is correct |
86 |
Correct |
1522 ms |
35964 KB |
Output is correct |
87 |
Correct |
1513 ms |
36120 KB |
Output is correct |
88 |
Correct |
1522 ms |
36076 KB |
Output is correct |
89 |
Correct |
732 ms |
31920 KB |
Output is correct |
90 |
Correct |
1525 ms |
36132 KB |
Output is correct |
91 |
Correct |
1376 ms |
36652 KB |
Output is correct |
92 |
Correct |
360 ms |
19388 KB |
Output is correct |
93 |
Correct |
723 ms |
27332 KB |
Output is correct |
94 |
Correct |
362 ms |
19300 KB |
Output is correct |
95 |
Correct |
382 ms |
19412 KB |
Output is correct |
96 |
Correct |
626 ms |
22020 KB |
Output is correct |
97 |
Correct |
787 ms |
31020 KB |
Output is correct |
98 |
Correct |
366 ms |
19360 KB |
Output is correct |
99 |
Correct |
863 ms |
30976 KB |
Output is correct |
100 |
Correct |
372 ms |
19548 KB |
Output is correct |