#include <bits/stdc++.h>
#define ford(i,n) for (int i = n-1; i >= 0; i--)
#pragma GCC diagnostic ignored "-Wunused-result"
using namespace std;
typedef pair<int, int> pii;
typedef pair<int, pii> Lien;
typedef priority_queue<pii, vector<pii>, greater<pii>> MinHeap;
const int INF = (INT_MAX - 3) / 2;
const int borneMax = (int)(1e5) + 5;
int nbNod, nbArc, nbCen, nbReq;
vector<pii> adj[borneMax];
vector<pii> mst[borneMax];
vector<int> cen;
vector<int> valeur(borneMax, INF);
bool exemple = false;
int pere[borneMax];
int depth[borneMax];
int ancetre[borneMax][18];
int minpoids[borneMax][18];
void lireEntree()
{
scanf("%d%d", &nbNod, &nbArc);
for (int ind = 0; ind < nbArc; ++ind)
{
int nod1, nod2, poids;
scanf("%d%d%d", &nod1, &nod2, &poids);
adj[nod1].push_back({nod2, poids});
adj[nod2].push_back({nod1, poids});
}
scanf("%d", &nbCen);
cen.resize(nbCen);
for (int ind = 0; ind < nbCen; ++ind)
{
scanf("%d", &cen[ind]);
}
}
void preparer()
{
MinHeap dij;
for (int nod : cen)
{
dij.push({nod, 0});
valeur[nod] = 0;
}
while (! dij.empty())
{
auto e = dij.top();
int nod = e.first, dis = e.second;
dij.pop();
if (dis > valeur[nod]) continue;
for (pii obj : adj[nod])
{
int voisin = obj.first, poids = obj.second;
if (dis + poids < valeur[voisin])
{
valeur[voisin] = dis + poids;
dij.push({voisin, dis + poids});
}
}
}
}
// Structure union-find optimisée en temps
// Complexité des opérations : O(log N)
class UnionFind
{
public:
UnionFind(int sz);
int findRepr(int elem);
bool unir(int a, int b);
private:
int taille;
vector<int> repr, couverts;
};
UnionFind::UnionFind(int sz) : taille(sz), repr(sz+1), couverts(sz+1)
{
for (int ind = 0; ind <= taille; ++ind)
{
repr[ind] = ind;
couverts[ind] = 1;
}
}
int UnionFind::findRepr(int elem)
{
stack<int> vus; // (!) Consommation mémoire pour optimisation temporelle
while (elem != repr[elem])
{
vus.push(elem);
elem = repr[elem];
}
// Compression de chemin
while (! vus.empty())
{
repr[vus.top()] = elem;
vus.pop();
}
return elem;
}
// Retourne vrai si les deux élements ont été unis (n'étaient pas dans la même composante)
bool UnionFind::unir(int a, int b)
{
a = findRepr(a);
b = findRepr(b);
if (a == b)
return false;
// Equilibrage : on insère le petit arbre dans le grand
if (couverts[a] > couverts[b])
swap(a, b);
repr[a] = b;
couverts[b] += couverts[a];
return true;
}
void kruskal()
{
vector<Lien> arcs;
for (int ind = 1; ind <= nbNod; ++ind)
{
for (auto voiraw : adj[ind])
{
int voisin = voiraw.first;
if (ind < voisin) arcs.push_back({-min(valeur[ind], valeur[voisin]), {ind, voisin}});
}
}
sort(arcs.begin(), arcs.end());
UnionFind uf(nbNod + 1);
for (auto arc : arcs)
{
int poids = -arc.first, nod1 = arc.second.first, nod2 = arc.second.second;
if (uf.unir(nod1, nod2))
{
mst[nod1].push_back({nod2, poids});
mst[nod2].push_back({nod1, poids});
}
}
}
void genInfos()
{
fill_n(&minpoids[0][0], borneMax * 18, INF);
pere[1] = depth[1] = 0;
stack<int> dfs;
dfs.push(1);
while (! dfs.empty())
{
int nod = dfs.top(); dfs.pop();
for (pii vo : mst[nod]) if (vo.first != pere[nod])
{
pere[vo.first] = ancetre[vo.first][0] = nod;
minpoids[vo.first][0] = vo.second;
depth[vo.first] = depth[nod] + 1;
dfs.push(vo.first);
}
}
dfs.push(1);
while (! dfs.empty())
{
int nod = dfs.top(); dfs.pop();
for (int k = 1; (1 << k) <= depth[nod]; ++k)
{
ancetre[nod][k] = ancetre[ancetre[nod][k-1]][k-1];
minpoids[nod][k] = min(minpoids[nod][k-1], minpoids[ancetre[nod][k-1]][k-1]);
}
for (pii vo : mst[nod]) if (vo.first != pere[nod])
{
dfs.push(vo.first);
}
}
}
int LCA(int u, int v)
{
if (depth[u] > depth[v]) swap(u, v); // v plus bas que u
ford(k, 18)
{
if (depth[v] - depth[u] >= (1 << k)) v = ancetre[v][k];
}
if (u == v) return u;
ford(k, 18)
{
if (depth[u] < (1 << k)) continue;
if (ancetre[u][k] != ancetre[v][k])
{
u = ancetre[u][k];
v = ancetre[v][k];
}
}
return pere[u];
}
int minTo(int nod, int par)
{
int m = INF;
ford(k, 18) if (depth[nod] - depth[par] >= (1 << k))
{
m = min(m, minpoids[nod][k]);
nod = ancetre[nod][k];
}
return m;
}
int main()
{
lireEntree();
preparer();
kruskal();
genInfos();
scanf("%d", &nbReq);
for (int ind = 0; ind < nbReq; ++ind)
{
int nod1, nod2;
scanf("%d%d", &nod1, &nod2);
int lc = LCA(nod1, nod2);
int m = min(minTo(nod1, lc), minTo(nod2, lc));
printf("%d\n", m);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12408 KB |
Output is correct |
2 |
Correct |
14 ms |
12664 KB |
Output is correct |
3 |
Correct |
14 ms |
12664 KB |
Output is correct |
4 |
Correct |
12 ms |
12408 KB |
Output is correct |
5 |
Correct |
14 ms |
12664 KB |
Output is correct |
6 |
Correct |
14 ms |
12664 KB |
Output is correct |
7 |
Correct |
13 ms |
12536 KB |
Output is correct |
8 |
Correct |
15 ms |
12536 KB |
Output is correct |
9 |
Correct |
15 ms |
12664 KB |
Output is correct |
10 |
Correct |
14 ms |
12664 KB |
Output is correct |
11 |
Correct |
14 ms |
12664 KB |
Output is correct |
12 |
Correct |
14 ms |
12664 KB |
Output is correct |
13 |
Correct |
15 ms |
12664 KB |
Output is correct |
14 |
Correct |
14 ms |
12664 KB |
Output is correct |
15 |
Correct |
14 ms |
12664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12408 KB |
Output is correct |
2 |
Correct |
14 ms |
12664 KB |
Output is correct |
3 |
Correct |
14 ms |
12664 KB |
Output is correct |
4 |
Correct |
12 ms |
12408 KB |
Output is correct |
5 |
Correct |
14 ms |
12664 KB |
Output is correct |
6 |
Correct |
14 ms |
12664 KB |
Output is correct |
7 |
Correct |
13 ms |
12536 KB |
Output is correct |
8 |
Correct |
15 ms |
12536 KB |
Output is correct |
9 |
Correct |
15 ms |
12664 KB |
Output is correct |
10 |
Correct |
14 ms |
12664 KB |
Output is correct |
11 |
Correct |
14 ms |
12664 KB |
Output is correct |
12 |
Correct |
14 ms |
12664 KB |
Output is correct |
13 |
Correct |
15 ms |
12664 KB |
Output is correct |
14 |
Correct |
14 ms |
12664 KB |
Output is correct |
15 |
Correct |
14 ms |
12664 KB |
Output is correct |
16 |
Correct |
354 ms |
25936 KB |
Output is correct |
17 |
Correct |
1654 ms |
46764 KB |
Output is correct |
18 |
Correct |
101 ms |
15428 KB |
Output is correct |
19 |
Correct |
351 ms |
30600 KB |
Output is correct |
20 |
Correct |
1624 ms |
46848 KB |
Output is correct |
21 |
Correct |
482 ms |
31072 KB |
Output is correct |
22 |
Correct |
291 ms |
28200 KB |
Output is correct |
23 |
Correct |
1481 ms |
46748 KB |
Output is correct |
24 |
Correct |
1333 ms |
40892 KB |
Output is correct |
25 |
Correct |
1052 ms |
37892 KB |
Output is correct |
26 |
Correct |
239 ms |
29124 KB |
Output is correct |
27 |
Correct |
237 ms |
29252 KB |
Output is correct |
28 |
Correct |
249 ms |
30324 KB |
Output is correct |
29 |
Correct |
256 ms |
30496 KB |
Output is correct |
30 |
Correct |
219 ms |
29248 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
12408 KB |
Output is correct |
2 |
Correct |
13 ms |
12536 KB |
Output is correct |
3 |
Correct |
16 ms |
12408 KB |
Output is correct |
4 |
Correct |
15 ms |
12408 KB |
Output is correct |
5 |
Correct |
13 ms |
12536 KB |
Output is correct |
6 |
Correct |
13 ms |
12412 KB |
Output is correct |
7 |
Correct |
13 ms |
12536 KB |
Output is correct |
8 |
Correct |
13 ms |
12408 KB |
Output is correct |
9 |
Correct |
13 ms |
12408 KB |
Output is correct |
10 |
Correct |
13 ms |
12408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
691 ms |
32980 KB |
Output is correct |
2 |
Correct |
1487 ms |
46408 KB |
Output is correct |
3 |
Correct |
1432 ms |
46308 KB |
Output is correct |
4 |
Correct |
217 ms |
27344 KB |
Output is correct |
5 |
Correct |
1234 ms |
40400 KB |
Output is correct |
6 |
Correct |
1217 ms |
40552 KB |
Output is correct |
7 |
Correct |
1180 ms |
40528 KB |
Output is correct |
8 |
Correct |
1371 ms |
46384 KB |
Output is correct |
9 |
Correct |
1478 ms |
46352 KB |
Output is correct |
10 |
Correct |
1451 ms |
46396 KB |
Output is correct |
11 |
Correct |
1353 ms |
46376 KB |
Output is correct |
12 |
Correct |
1120 ms |
40496 KB |
Output is correct |
13 |
Correct |
1089 ms |
40480 KB |
Output is correct |
14 |
Correct |
1002 ms |
37584 KB |
Output is correct |
15 |
Correct |
903 ms |
37628 KB |
Output is correct |
16 |
Correct |
1020 ms |
40592 KB |
Output is correct |
17 |
Correct |
1133 ms |
40604 KB |
Output is correct |
18 |
Correct |
1444 ms |
46392 KB |
Output is correct |
19 |
Correct |
207 ms |
27348 KB |
Output is correct |
20 |
Correct |
1250 ms |
40516 KB |
Output is correct |
21 |
Correct |
770 ms |
38036 KB |
Output is correct |
22 |
Correct |
183 ms |
28836 KB |
Output is correct |
23 |
Correct |
231 ms |
28400 KB |
Output is correct |
24 |
Correct |
155 ms |
28888 KB |
Output is correct |
25 |
Correct |
179 ms |
28936 KB |
Output is correct |
26 |
Correct |
252 ms |
28272 KB |
Output is correct |
27 |
Correct |
218 ms |
27344 KB |
Output is correct |
28 |
Correct |
154 ms |
28872 KB |
Output is correct |
29 |
Correct |
220 ms |
27396 KB |
Output is correct |
30 |
Correct |
157 ms |
28868 KB |
Output is correct |
31 |
Correct |
218 ms |
27348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
12408 KB |
Output is correct |
2 |
Correct |
14 ms |
12664 KB |
Output is correct |
3 |
Correct |
14 ms |
12664 KB |
Output is correct |
4 |
Correct |
12 ms |
12408 KB |
Output is correct |
5 |
Correct |
14 ms |
12664 KB |
Output is correct |
6 |
Correct |
14 ms |
12664 KB |
Output is correct |
7 |
Correct |
13 ms |
12536 KB |
Output is correct |
8 |
Correct |
15 ms |
12536 KB |
Output is correct |
9 |
Correct |
15 ms |
12664 KB |
Output is correct |
10 |
Correct |
14 ms |
12664 KB |
Output is correct |
11 |
Correct |
14 ms |
12664 KB |
Output is correct |
12 |
Correct |
14 ms |
12664 KB |
Output is correct |
13 |
Correct |
15 ms |
12664 KB |
Output is correct |
14 |
Correct |
14 ms |
12664 KB |
Output is correct |
15 |
Correct |
14 ms |
12664 KB |
Output is correct |
16 |
Correct |
354 ms |
25936 KB |
Output is correct |
17 |
Correct |
1654 ms |
46764 KB |
Output is correct |
18 |
Correct |
101 ms |
15428 KB |
Output is correct |
19 |
Correct |
351 ms |
30600 KB |
Output is correct |
20 |
Correct |
1624 ms |
46848 KB |
Output is correct |
21 |
Correct |
482 ms |
31072 KB |
Output is correct |
22 |
Correct |
291 ms |
28200 KB |
Output is correct |
23 |
Correct |
1481 ms |
46748 KB |
Output is correct |
24 |
Correct |
1333 ms |
40892 KB |
Output is correct |
25 |
Correct |
1052 ms |
37892 KB |
Output is correct |
26 |
Correct |
239 ms |
29124 KB |
Output is correct |
27 |
Correct |
237 ms |
29252 KB |
Output is correct |
28 |
Correct |
249 ms |
30324 KB |
Output is correct |
29 |
Correct |
256 ms |
30496 KB |
Output is correct |
30 |
Correct |
219 ms |
29248 KB |
Output is correct |
31 |
Correct |
13 ms |
12408 KB |
Output is correct |
32 |
Correct |
13 ms |
12536 KB |
Output is correct |
33 |
Correct |
16 ms |
12408 KB |
Output is correct |
34 |
Correct |
15 ms |
12408 KB |
Output is correct |
35 |
Correct |
13 ms |
12536 KB |
Output is correct |
36 |
Correct |
13 ms |
12412 KB |
Output is correct |
37 |
Correct |
13 ms |
12536 KB |
Output is correct |
38 |
Correct |
13 ms |
12408 KB |
Output is correct |
39 |
Correct |
13 ms |
12408 KB |
Output is correct |
40 |
Correct |
13 ms |
12408 KB |
Output is correct |
41 |
Correct |
691 ms |
32980 KB |
Output is correct |
42 |
Correct |
1487 ms |
46408 KB |
Output is correct |
43 |
Correct |
1432 ms |
46308 KB |
Output is correct |
44 |
Correct |
217 ms |
27344 KB |
Output is correct |
45 |
Correct |
1234 ms |
40400 KB |
Output is correct |
46 |
Correct |
1217 ms |
40552 KB |
Output is correct |
47 |
Correct |
1180 ms |
40528 KB |
Output is correct |
48 |
Correct |
1371 ms |
46384 KB |
Output is correct |
49 |
Correct |
1478 ms |
46352 KB |
Output is correct |
50 |
Correct |
1451 ms |
46396 KB |
Output is correct |
51 |
Correct |
1353 ms |
46376 KB |
Output is correct |
52 |
Correct |
1120 ms |
40496 KB |
Output is correct |
53 |
Correct |
1089 ms |
40480 KB |
Output is correct |
54 |
Correct |
1002 ms |
37584 KB |
Output is correct |
55 |
Correct |
903 ms |
37628 KB |
Output is correct |
56 |
Correct |
1020 ms |
40592 KB |
Output is correct |
57 |
Correct |
1133 ms |
40604 KB |
Output is correct |
58 |
Correct |
1444 ms |
46392 KB |
Output is correct |
59 |
Correct |
207 ms |
27348 KB |
Output is correct |
60 |
Correct |
1250 ms |
40516 KB |
Output is correct |
61 |
Correct |
770 ms |
38036 KB |
Output is correct |
62 |
Correct |
183 ms |
28836 KB |
Output is correct |
63 |
Correct |
231 ms |
28400 KB |
Output is correct |
64 |
Correct |
155 ms |
28888 KB |
Output is correct |
65 |
Correct |
179 ms |
28936 KB |
Output is correct |
66 |
Correct |
252 ms |
28272 KB |
Output is correct |
67 |
Correct |
218 ms |
27344 KB |
Output is correct |
68 |
Correct |
154 ms |
28872 KB |
Output is correct |
69 |
Correct |
220 ms |
27396 KB |
Output is correct |
70 |
Correct |
157 ms |
28868 KB |
Output is correct |
71 |
Correct |
218 ms |
27348 KB |
Output is correct |
72 |
Correct |
720 ms |
31964 KB |
Output is correct |
73 |
Correct |
1418 ms |
43776 KB |
Output is correct |
74 |
Correct |
1348 ms |
44092 KB |
Output is correct |
75 |
Correct |
1718 ms |
48828 KB |
Output is correct |
76 |
Correct |
1345 ms |
43812 KB |
Output is correct |
77 |
Correct |
1300 ms |
43400 KB |
Output is correct |
78 |
Correct |
1533 ms |
49628 KB |
Output is correct |
79 |
Correct |
1508 ms |
48792 KB |
Output is correct |
80 |
Correct |
1528 ms |
47652 KB |
Output is correct |
81 |
Correct |
1527 ms |
48356 KB |
Output is correct |
82 |
Correct |
1226 ms |
41984 KB |
Output is correct |
83 |
Correct |
1201 ms |
41700 KB |
Output is correct |
84 |
Correct |
1086 ms |
38960 KB |
Output is correct |
85 |
Correct |
1016 ms |
39584 KB |
Output is correct |
86 |
Correct |
1171 ms |
42584 KB |
Output is correct |
87 |
Correct |
1360 ms |
41700 KB |
Output is correct |
88 |
Correct |
1546 ms |
47836 KB |
Output is correct |
89 |
Correct |
374 ms |
28808 KB |
Output is correct |
90 |
Correct |
1473 ms |
48172 KB |
Output is correct |
91 |
Correct |
893 ms |
39892 KB |
Output is correct |
92 |
Correct |
242 ms |
29980 KB |
Output is correct |
93 |
Correct |
347 ms |
29784 KB |
Output is correct |
94 |
Correct |
239 ms |
29740 KB |
Output is correct |
95 |
Correct |
236 ms |
29868 KB |
Output is correct |
96 |
Correct |
352 ms |
29264 KB |
Output is correct |
97 |
Correct |
382 ms |
28468 KB |
Output is correct |
98 |
Correct |
239 ms |
29640 KB |
Output is correct |
99 |
Correct |
375 ms |
28368 KB |
Output is correct |
100 |
Correct |
237 ms |
29924 KB |
Output is correct |