#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = LLONG_MAX/6;
vector<int> parentUF;
vector<vector<int>> voisinDeArbre;
vector<int> pereDe;
vector<vector<int>> filsDe;
vector<int > profNde;
int getLeader(int nde)
{
if(parentUF[nde] == nde)
return nde;
parentUF[nde] = getLeader(parentUF[nde]);
return parentUF[nde];
}
void mergeUF(int u, int v)
{
int leaderU = getLeader(u);
int leaderV = getLeader(v);
if(leaderU != leaderV)
parentUF[leaderU] = leaderV;
}
void dfsRoot(int nde, int ancestor, int prof)
{
pereDe[nde] = ancestor;
profNde[nde] = prof;
for(int iV : voisinDeArbre[nde])
{
if(iV != ancestor)
{
filsDe[nde].push_back(iV);
dfsRoot(iV, nde, prof+1);
}
}
}
signed main()
{
int nbNdes, nbArcs;
scanf("%lld%lld", &nbNdes, &nbArcs);
vector<vector<pair<int, int>>> voisinDe(nbNdes);
vector<pair<int, int>> arcs;
vector<tuple<int, int, int>> arcsSorted;
for(int iA = 0; iA< nbArcs; iA++)
{
int u, v, pond;
scanf("%lld%lld%lld", &u, &v, &pond);
u--;v--;
voisinDe[u].push_back({pond, v});
voisinDe[v].push_back({pond, u});
arcs.push_back({u, v});
}
int nbSpe;
scanf("%lld", &nbSpe);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for(int iSpe = 0; iSpe < nbSpe; iSpe++)
{
int u;
scanf("%lld", &u);
u--;
pq.push({0, u});
}
vector<int> pondNde(nbNdes, INF);
while (!pq.empty())
{
pair<int, int> pqTop = pq.top();
pq.pop();
int pondAct = pqTop.first;
int ndeAct = pqTop.second;
if(pondNde[ndeAct] == INF)
{
pondNde[ndeAct] = pondAct;
for(pair<int, int> iV : voisinDe[ndeAct])
{
pq.push({pondAct + iV.first, iV.second});
}
}
}
for(int iArc = 0; iArc< nbArcs; iArc++)
{
int u = arcs[iArc].first, v = arcs[iArc].second;
int pondArc = min(pondNde[u], pondNde[v]);
arcsSorted.push_back({-pondArc, u, v});
}
sort(arcsSorted.begin(), arcsSorted.end());
parentUF.resize(nbNdes);
for(int iNde = 0; iNde< nbNdes; iNde++)
{
parentUF[iNde] = iNde;
}
voisinDeArbre.resize(nbNdes);
for(tuple<int, int, int> arcAct: arcsSorted)
{
int u = get<1>(arcAct);
int v = get<2>(arcAct);
if(getLeader(u) != getLeader(v))
{
mergeUF(u, v);
voisinDeArbre[u].push_back(v);
voisinDeArbre[v].push_back(u);
}
}
pereDe.resize(nbNdes);
filsDe.resize(nbNdes);
profNde.resize(nbNdes);
int root = 0;
dfsRoot(root, root, 0);
vector<vector<int>> goUpValue(nbNdes, vector<int>(20));
vector<vector<int>> goUpCrtq(nbNdes, vector<int>(20));
for(int iNde = 0; iNde< nbNdes; iNde++)
{
goUpValue[iNde][0] = pereDe[iNde];
goUpCrtq[iNde][0] = min(pondNde[iNde], pondNde[pereDe[iNde]]);
}
for(int powerTwo = 1; powerTwo< 20; powerTwo++)
{
for(int iNde = 0; iNde < nbNdes; iNde++)
{
goUpValue[iNde][powerTwo] = goUpValue[goUpValue[iNde][powerTwo-1]][powerTwo-1];
goUpCrtq[iNde][powerTwo] = min(goUpCrtq[iNde][powerTwo-1], goUpCrtq[goUpValue[iNde][powerTwo-1]][powerTwo-1]);
}
}
int nbQueries;
scanf("%lld", &nbQueries);
for(int iQ =0; iQ< nbQueries; iQ++)
{
int u, v;
scanf("%lld%lld", &u, &v);
u--;
v--;
int minCtrqWh = min(pondNde[u], pondNde[v]);
if(profNde[u]>profNde[v])
{
int tmp = u;
u = v;
v = tmp;
}
for(int powerTwo = 19; powerTwo>=0; powerTwo--)
{
if(profNde[v] - (1 << powerTwo) >= profNde[u])
{
minCtrqWh = min(minCtrqWh, goUpCrtq[v][powerTwo]);
v = goUpValue[v][powerTwo];
}
}
for(int powerTwo = 19; powerTwo>=0; powerTwo--)
{
if(goUpValue[u][powerTwo] != goUpValue[v][powerTwo])
{
minCtrqWh = min(minCtrqWh, goUpCrtq[u][powerTwo]);
u = goUpValue[u][powerTwo];
minCtrqWh = min(minCtrqWh, goUpCrtq[v][powerTwo]);
v = goUpValue[v][powerTwo];
}
}
if(u != v)
{
minCtrqWh = min(minCtrqWh, goUpCrtq[u][0]);
}
printf("%lld\n", minCtrqWh);
}
}
Compilation message
plan.cpp: In function 'int main()':
plan.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
47 | scanf("%lld%lld", &nbNdes, &nbArcs);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%lld%lld%lld", &u, &v, &pond);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plan.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
61 | scanf("%lld", &nbSpe);
| ~~~~~^~~~~~~~~~~~~~~~
plan.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%lld", &u);
| ~~~~~^~~~~~~~~~~~
plan.cpp:136:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
136 | scanf("%lld", &nbQueries);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
plan.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | scanf("%lld%lld", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
1120 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
1112 KB |
Output is correct |
10 |
Correct |
2 ms |
1116 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
2 ms |
860 KB |
Output is correct |
14 |
Correct |
2 ms |
1112 KB |
Output is correct |
15 |
Correct |
2 ms |
1092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
1120 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
1112 KB |
Output is correct |
10 |
Correct |
2 ms |
1116 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
2 ms |
860 KB |
Output is correct |
14 |
Correct |
2 ms |
1112 KB |
Output is correct |
15 |
Correct |
2 ms |
1092 KB |
Output is correct |
16 |
Correct |
203 ms |
56084 KB |
Output is correct |
17 |
Correct |
655 ms |
120612 KB |
Output is correct |
18 |
Correct |
40 ms |
12104 KB |
Output is correct |
19 |
Correct |
187 ms |
68144 KB |
Output is correct |
20 |
Correct |
639 ms |
120572 KB |
Output is correct |
21 |
Correct |
343 ms |
83128 KB |
Output is correct |
22 |
Correct |
226 ms |
76068 KB |
Output is correct |
23 |
Correct |
654 ms |
119500 KB |
Output is correct |
24 |
Correct |
614 ms |
119080 KB |
Output is correct |
25 |
Correct |
653 ms |
119004 KB |
Output is correct |
26 |
Correct |
204 ms |
67928 KB |
Output is correct |
27 |
Correct |
189 ms |
67656 KB |
Output is correct |
28 |
Correct |
198 ms |
67564 KB |
Output is correct |
29 |
Correct |
186 ms |
67824 KB |
Output is correct |
30 |
Correct |
193 ms |
67892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
436 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
279 ms |
78452 KB |
Output is correct |
2 |
Correct |
575 ms |
118304 KB |
Output is correct |
3 |
Correct |
553 ms |
116728 KB |
Output is correct |
4 |
Correct |
168 ms |
71096 KB |
Output is correct |
5 |
Correct |
557 ms |
118308 KB |
Output is correct |
6 |
Correct |
567 ms |
117164 KB |
Output is correct |
7 |
Correct |
567 ms |
116784 KB |
Output is correct |
8 |
Correct |
575 ms |
118304 KB |
Output is correct |
9 |
Correct |
584 ms |
117344 KB |
Output is correct |
10 |
Correct |
572 ms |
117848 KB |
Output is correct |
11 |
Correct |
559 ms |
117452 KB |
Output is correct |
12 |
Correct |
561 ms |
117300 KB |
Output is correct |
13 |
Correct |
587 ms |
116852 KB |
Output is correct |
14 |
Correct |
574 ms |
118192 KB |
Output is correct |
15 |
Correct |
567 ms |
117420 KB |
Output is correct |
16 |
Correct |
564 ms |
117940 KB |
Output is correct |
17 |
Correct |
589 ms |
117416 KB |
Output is correct |
18 |
Correct |
593 ms |
117420 KB |
Output is correct |
19 |
Correct |
167 ms |
73660 KB |
Output is correct |
20 |
Correct |
558 ms |
117888 KB |
Output is correct |
21 |
Correct |
592 ms |
121476 KB |
Output is correct |
22 |
Correct |
142 ms |
66100 KB |
Output is correct |
23 |
Correct |
166 ms |
66952 KB |
Output is correct |
24 |
Correct |
141 ms |
66200 KB |
Output is correct |
25 |
Correct |
157 ms |
66616 KB |
Output is correct |
26 |
Correct |
168 ms |
67260 KB |
Output is correct |
27 |
Correct |
174 ms |
73356 KB |
Output is correct |
28 |
Correct |
155 ms |
66536 KB |
Output is correct |
29 |
Correct |
182 ms |
72380 KB |
Output is correct |
30 |
Correct |
144 ms |
66188 KB |
Output is correct |
31 |
Correct |
179 ms |
72384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
1108 KB |
Output is correct |
3 |
Correct |
1 ms |
860 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
1120 KB |
Output is correct |
6 |
Correct |
2 ms |
1116 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
2 ms |
1112 KB |
Output is correct |
10 |
Correct |
2 ms |
1116 KB |
Output is correct |
11 |
Correct |
1 ms |
860 KB |
Output is correct |
12 |
Correct |
1 ms |
860 KB |
Output is correct |
13 |
Correct |
2 ms |
860 KB |
Output is correct |
14 |
Correct |
2 ms |
1112 KB |
Output is correct |
15 |
Correct |
2 ms |
1092 KB |
Output is correct |
16 |
Correct |
203 ms |
56084 KB |
Output is correct |
17 |
Correct |
655 ms |
120612 KB |
Output is correct |
18 |
Correct |
40 ms |
12104 KB |
Output is correct |
19 |
Correct |
187 ms |
68144 KB |
Output is correct |
20 |
Correct |
639 ms |
120572 KB |
Output is correct |
21 |
Correct |
343 ms |
83128 KB |
Output is correct |
22 |
Correct |
226 ms |
76068 KB |
Output is correct |
23 |
Correct |
654 ms |
119500 KB |
Output is correct |
24 |
Correct |
614 ms |
119080 KB |
Output is correct |
25 |
Correct |
653 ms |
119004 KB |
Output is correct |
26 |
Correct |
204 ms |
67928 KB |
Output is correct |
27 |
Correct |
189 ms |
67656 KB |
Output is correct |
28 |
Correct |
198 ms |
67564 KB |
Output is correct |
29 |
Correct |
186 ms |
67824 KB |
Output is correct |
30 |
Correct |
193 ms |
67892 KB |
Output is correct |
31 |
Correct |
0 ms |
348 KB |
Output is correct |
32 |
Correct |
0 ms |
348 KB |
Output is correct |
33 |
Correct |
0 ms |
344 KB |
Output is correct |
34 |
Correct |
1 ms |
348 KB |
Output is correct |
35 |
Correct |
0 ms |
348 KB |
Output is correct |
36 |
Correct |
0 ms |
436 KB |
Output is correct |
37 |
Correct |
0 ms |
348 KB |
Output is correct |
38 |
Correct |
0 ms |
348 KB |
Output is correct |
39 |
Correct |
0 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
279 ms |
78452 KB |
Output is correct |
42 |
Correct |
575 ms |
118304 KB |
Output is correct |
43 |
Correct |
553 ms |
116728 KB |
Output is correct |
44 |
Correct |
168 ms |
71096 KB |
Output is correct |
45 |
Correct |
557 ms |
118308 KB |
Output is correct |
46 |
Correct |
567 ms |
117164 KB |
Output is correct |
47 |
Correct |
567 ms |
116784 KB |
Output is correct |
48 |
Correct |
575 ms |
118304 KB |
Output is correct |
49 |
Correct |
584 ms |
117344 KB |
Output is correct |
50 |
Correct |
572 ms |
117848 KB |
Output is correct |
51 |
Correct |
559 ms |
117452 KB |
Output is correct |
52 |
Correct |
561 ms |
117300 KB |
Output is correct |
53 |
Correct |
587 ms |
116852 KB |
Output is correct |
54 |
Correct |
574 ms |
118192 KB |
Output is correct |
55 |
Correct |
567 ms |
117420 KB |
Output is correct |
56 |
Correct |
564 ms |
117940 KB |
Output is correct |
57 |
Correct |
589 ms |
117416 KB |
Output is correct |
58 |
Correct |
593 ms |
117420 KB |
Output is correct |
59 |
Correct |
167 ms |
73660 KB |
Output is correct |
60 |
Correct |
558 ms |
117888 KB |
Output is correct |
61 |
Correct |
592 ms |
121476 KB |
Output is correct |
62 |
Correct |
142 ms |
66100 KB |
Output is correct |
63 |
Correct |
166 ms |
66952 KB |
Output is correct |
64 |
Correct |
141 ms |
66200 KB |
Output is correct |
65 |
Correct |
157 ms |
66616 KB |
Output is correct |
66 |
Correct |
168 ms |
67260 KB |
Output is correct |
67 |
Correct |
174 ms |
73356 KB |
Output is correct |
68 |
Correct |
155 ms |
66536 KB |
Output is correct |
69 |
Correct |
182 ms |
72380 KB |
Output is correct |
70 |
Correct |
144 ms |
66188 KB |
Output is correct |
71 |
Correct |
179 ms |
72384 KB |
Output is correct |
72 |
Correct |
391 ms |
80296 KB |
Output is correct |
73 |
Correct |
659 ms |
118568 KB |
Output is correct |
74 |
Correct |
657 ms |
119276 KB |
Output is correct |
75 |
Correct |
689 ms |
120092 KB |
Output is correct |
76 |
Correct |
652 ms |
118664 KB |
Output is correct |
77 |
Correct |
660 ms |
120964 KB |
Output is correct |
78 |
Correct |
668 ms |
119400 KB |
Output is correct |
79 |
Correct |
649 ms |
118272 KB |
Output is correct |
80 |
Correct |
665 ms |
118332 KB |
Output is correct |
81 |
Correct |
673 ms |
120012 KB |
Output is correct |
82 |
Correct |
668 ms |
120436 KB |
Output is correct |
83 |
Correct |
662 ms |
120400 KB |
Output is correct |
84 |
Correct |
690 ms |
118544 KB |
Output is correct |
85 |
Correct |
668 ms |
119272 KB |
Output is correct |
86 |
Correct |
646 ms |
119016 KB |
Output is correct |
87 |
Correct |
669 ms |
119044 KB |
Output is correct |
88 |
Correct |
681 ms |
118820 KB |
Output is correct |
89 |
Correct |
342 ms |
74416 KB |
Output is correct |
90 |
Correct |
641 ms |
119676 KB |
Output is correct |
91 |
Correct |
649 ms |
121020 KB |
Output is correct |
92 |
Correct |
214 ms |
67636 KB |
Output is correct |
93 |
Correct |
276 ms |
69032 KB |
Output is correct |
94 |
Correct |
211 ms |
67752 KB |
Output is correct |
95 |
Correct |
223 ms |
67860 KB |
Output is correct |
96 |
Correct |
285 ms |
69156 KB |
Output is correct |
97 |
Correct |
337 ms |
73056 KB |
Output is correct |
98 |
Correct |
229 ms |
67948 KB |
Output is correct |
99 |
Correct |
341 ms |
75068 KB |
Output is correct |
100 |
Correct |
224 ms |
67820 KB |
Output is correct |