#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> haha[100001];
vector<int> bruh(100001,INT_MAX);
vector<pair<int,int>> dsu[100001];
int dude(int x, int a) {
int l = 0,r = dsu[x].size()-1;
while(l < r) {
int m = (l+r+1)/2;
if(dsu[x][m].first >= a) {
l = m;
}
else {
r = m-1;
}
}
return dsu[x][l].second;
}
int calc(int a, int t) {
int c = a;
while(true) {
int d = dude(c,t);
if(d == c) {
return d;
}
c = d;
}
}
void upd(int a, int b, int t) {
int c = calc(a,-1),d = calc(b,-1);
if(c != d) {
dsu[c].push_back({t,d});
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n,m,a,b,c,k,q;
cin >> n >> m;
for(int i = 1; i <= n; i++) {
dsu[i].push_back({0,i});
}
for(int i = 0; i < m; i++) {
cin >> a >> b >> c;
haha[a].push_back({b,c});
haha[b].push_back({a,c});
}
cin >> k;
priority_queue<pair<int,int>> idk;
for(int i = 0; i < k; i++) {
cin >> a;
idk.push({0,a});
bruh[a] = 0;
}
while(!idk.empty()) {
a = -idk.top().first;
b = idk.top().second;
idk.pop();
if(bruh[b] < a) {
continue;
}
for(pair<int,int> v: haha[b]) {
if(v.second+a < bruh[v.first]) {
bruh[v.first] = v.second+a;
idk.push({-v.second-a,v.first});
}
}
}
vector<pair<int,int>> wut(0);
for(int i = 1; i <= n; i++) {
wut.push_back({bruh[i],i});
}
sort(wut.begin(),wut.end());
reverse(wut.begin(),wut.end());
for(int i = 0; i < n; i++) {
int s = wut[i].second;
for(pair<int,int> v: haha[s]) {
if(bruh[v.first] >= bruh[s]) {
upd(s,v.first,wut[i].first);
}
}
}
cin >> q;
for(int i = 0; i < q; i++) {
cin >> a >> b;
int l = 0,r = 1e9;
while(l < r) {
int m = (l+r+1)/2;
if(calc(a,m) == calc(b,m)) {
l = m;
}
else {
r = m-1;
}
}
cout << l << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5464 KB |
Output is correct |
2 |
Correct |
81 ms |
5468 KB |
Output is correct |
3 |
Correct |
55 ms |
5468 KB |
Output is correct |
4 |
Correct |
2 ms |
5720 KB |
Output is correct |
5 |
Correct |
47 ms |
5468 KB |
Output is correct |
6 |
Correct |
18 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
2 ms |
5464 KB |
Output is correct |
9 |
Correct |
3 ms |
5468 KB |
Output is correct |
10 |
Correct |
2 ms |
5468 KB |
Output is correct |
11 |
Correct |
3 ms |
5556 KB |
Output is correct |
12 |
Correct |
80 ms |
5468 KB |
Output is correct |
13 |
Correct |
3 ms |
5468 KB |
Output is correct |
14 |
Correct |
3 ms |
5468 KB |
Output is correct |
15 |
Correct |
3 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5464 KB |
Output is correct |
2 |
Correct |
81 ms |
5468 KB |
Output is correct |
3 |
Correct |
55 ms |
5468 KB |
Output is correct |
4 |
Correct |
2 ms |
5720 KB |
Output is correct |
5 |
Correct |
47 ms |
5468 KB |
Output is correct |
6 |
Correct |
18 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
2 ms |
5464 KB |
Output is correct |
9 |
Correct |
3 ms |
5468 KB |
Output is correct |
10 |
Correct |
2 ms |
5468 KB |
Output is correct |
11 |
Correct |
3 ms |
5556 KB |
Output is correct |
12 |
Correct |
80 ms |
5468 KB |
Output is correct |
13 |
Correct |
3 ms |
5468 KB |
Output is correct |
14 |
Correct |
3 ms |
5468 KB |
Output is correct |
15 |
Correct |
3 ms |
5468 KB |
Output is correct |
16 |
Execution timed out |
4046 ms |
14608 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
5468 KB |
Output is correct |
2 |
Correct |
2 ms |
5468 KB |
Output is correct |
3 |
Correct |
1 ms |
5468 KB |
Output is correct |
4 |
Correct |
1 ms |
5468 KB |
Output is correct |
5 |
Correct |
1 ms |
5464 KB |
Output is correct |
6 |
Correct |
2 ms |
5468 KB |
Output is correct |
7 |
Correct |
1 ms |
5468 KB |
Output is correct |
8 |
Correct |
2 ms |
5468 KB |
Output is correct |
9 |
Correct |
2 ms |
5468 KB |
Output is correct |
10 |
Correct |
2 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4027 ms |
19788 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5464 KB |
Output is correct |
2 |
Correct |
81 ms |
5468 KB |
Output is correct |
3 |
Correct |
55 ms |
5468 KB |
Output is correct |
4 |
Correct |
2 ms |
5720 KB |
Output is correct |
5 |
Correct |
47 ms |
5468 KB |
Output is correct |
6 |
Correct |
18 ms |
5468 KB |
Output is correct |
7 |
Correct |
2 ms |
5468 KB |
Output is correct |
8 |
Correct |
2 ms |
5464 KB |
Output is correct |
9 |
Correct |
3 ms |
5468 KB |
Output is correct |
10 |
Correct |
2 ms |
5468 KB |
Output is correct |
11 |
Correct |
3 ms |
5556 KB |
Output is correct |
12 |
Correct |
80 ms |
5468 KB |
Output is correct |
13 |
Correct |
3 ms |
5468 KB |
Output is correct |
14 |
Correct |
3 ms |
5468 KB |
Output is correct |
15 |
Correct |
3 ms |
5468 KB |
Output is correct |
16 |
Execution timed out |
4046 ms |
14608 KB |
Time limit exceeded |
17 |
Halted |
0 ms |
0 KB |
- |