#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 500000
#define LOG 20
#define INF 1000000000000000000
using namespace std;
///ifstream cin ("c.in");
///ofstream cout ("c.out");
vector <pair<int, long long>> graph[MAX + 10], length[MAX + 10];
vector <int> nodes, v;
int timer = 1, level[MAX + 10], in[MAX + 10], ancestor[LOG + 10][MAX + 10], company[MAX + 10], visited[MAX + 10];
long long dist[MAX + 10], dp1[MAX + 10], dp2[MAX + 10], ans;
///int a[MAX + 10], b[MAX + 10], d[MAX + 10], x[MAX + 10], y[MAX + 10];
void dfs(int node, int parent)
{
in[node] = timer;
timer++;
level[node] = level[parent] + 1;
ancestor[0][node] = parent;
for (auto next : graph[node])
if (next.first != parent)
{
dist[next.first] = dist[node] + next.second;
dfs(next.first, node);
}
}
void Init(int n, int a[], int b[], int d[])
{
for (int i = 0; i < n - 1; i++)
{
graph[a[i] + 1].push_back({b[i] + 1, d[i]});
graph[b[i] + 1].push_back({a[i] + 1, d[i]});
}
dfs(1, 0);
for (int p = 1; p <= LOG; p++)
for (int node = 1; node <= n; node++)
ancestor[p][node] = ancestor[p - 1][ancestor[p - 1][node]];
for (int node = 1; node <= n; node++)
{
dp1[node] = INF;
dp2[node] = INF;
}
}
bool cmp(int i, int j)
{
return (in[i] < in[j]);
}
int lca(int node1, int node2)
{
if (level[node1] < level[node2])
swap(node1, node2);
int diff = level[node1] - level[node2];
for (int p = LOG; p >= 0; p--)
if (diff >> p & 1)
node1 = ancestor[p][node1];
if (node1 == node2)
return node1;
for (int p = LOG; p >= 0; p--)
if (ancestor[p][node1] != 0 && ancestor[p][node2] != 0)
if (ancestor[p][node1] != ancestor[p][node2])
{
node1 = ancestor[p][node1];
node2 = ancestor[p][node2];
}
return ancestor[0][node1];
}
void solve(int node)
{
if (company[node] == 1)
dp1[node] = 0;
if (company[node] == 2)
dp2[node] = 0;
for (auto next : length[node])
{
solve(next.first);
dp1[node] = min(dp1[node], dp1[next.first] + next.second);
dp2[node] = min(dp2[node], dp2[next.first] + next.second);
}
ans = min(ans, dp1[node] + dp2[node]);
}
long long Query(int s, int x[], int t, int y[])
{
for (int i = 0; i < s; i++)
{
visited[x[i] + 1] = 1;
company[x[i] + 1] = 1;
nodes.push_back(x[i] + 1);
}
for (int i = 0; i < t; i++)
{
visited[y[i] + 1] = 1;
company[y[i] + 1] = 2;
nodes.push_back(y[i] + 1);
}
sort(nodes.begin(), nodes.end(), cmp);
for (int i = 1; i < nodes.size(); i++)
if (visited[lca(nodes[i - 1], nodes[i])] == 0)
{
visited[lca(nodes[i - 1], nodes[i])] = 1;
nodes.push_back(lca(nodes[i - 1], nodes[i]));
}
sort(nodes.begin(), nodes.end(), cmp);
for (auto node : nodes)
{
if (!v.empty())
{
while (!v.empty() && lca(node, v.back()) != v.back())
v.pop_back();
length[v.back()].push_back({node, dist[node] + dist[v.back()] - 2 * dist[lca(node, v.back())]});
}
v.push_back(node);
}
ans = INF;
solve(v[0]);
for (int i = 0; i < s; i++)
company[x[i] + 1] = 0;
for (int i = 0; i < t; i++)
company[y[i] + 1] = 0;
for (auto node : nodes)
{
dp1[node] = INF;
dp2[node] = INF;
visited[node] = 0;
length[node].clear();
}
nodes.clear();
v.clear();
return ans;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for (int i = 1; i < nodes.size(); i++)
| ~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
24368 KB |
Output is correct |
2 |
Correct |
1150 ms |
33128 KB |
Output is correct |
3 |
Correct |
1471 ms |
33384 KB |
Output is correct |
4 |
Correct |
1242 ms |
33228 KB |
Output is correct |
5 |
Correct |
894 ms |
33404 KB |
Output is correct |
6 |
Correct |
884 ms |
33100 KB |
Output is correct |
7 |
Correct |
1524 ms |
33132 KB |
Output is correct |
8 |
Correct |
1269 ms |
33356 KB |
Output is correct |
9 |
Correct |
912 ms |
33292 KB |
Output is correct |
10 |
Correct |
925 ms |
33188 KB |
Output is correct |
11 |
Correct |
1511 ms |
33164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
24148 KB |
Output is correct |
2 |
Correct |
2262 ms |
122980 KB |
Output is correct |
3 |
Correct |
3883 ms |
127424 KB |
Output is correct |
4 |
Correct |
1258 ms |
138884 KB |
Output is correct |
5 |
Correct |
2000 ms |
180472 KB |
Output is correct |
6 |
Correct |
4250 ms |
147412 KB |
Output is correct |
7 |
Correct |
3579 ms |
66924 KB |
Output is correct |
8 |
Correct |
1471 ms |
66188 KB |
Output is correct |
9 |
Correct |
2320 ms |
73176 KB |
Output is correct |
10 |
Correct |
4209 ms |
68184 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
24368 KB |
Output is correct |
2 |
Correct |
1150 ms |
33128 KB |
Output is correct |
3 |
Correct |
1471 ms |
33384 KB |
Output is correct |
4 |
Correct |
1242 ms |
33228 KB |
Output is correct |
5 |
Correct |
894 ms |
33404 KB |
Output is correct |
6 |
Correct |
884 ms |
33100 KB |
Output is correct |
7 |
Correct |
1524 ms |
33132 KB |
Output is correct |
8 |
Correct |
1269 ms |
33356 KB |
Output is correct |
9 |
Correct |
912 ms |
33292 KB |
Output is correct |
10 |
Correct |
925 ms |
33188 KB |
Output is correct |
11 |
Correct |
1511 ms |
33164 KB |
Output is correct |
12 |
Correct |
16 ms |
24148 KB |
Output is correct |
13 |
Correct |
2262 ms |
122980 KB |
Output is correct |
14 |
Correct |
3883 ms |
127424 KB |
Output is correct |
15 |
Correct |
1258 ms |
138884 KB |
Output is correct |
16 |
Correct |
2000 ms |
180472 KB |
Output is correct |
17 |
Correct |
4250 ms |
147412 KB |
Output is correct |
18 |
Correct |
3579 ms |
66924 KB |
Output is correct |
19 |
Correct |
1471 ms |
66188 KB |
Output is correct |
20 |
Correct |
2320 ms |
73176 KB |
Output is correct |
21 |
Correct |
4209 ms |
68184 KB |
Output is correct |
22 |
Correct |
4668 ms |
157616 KB |
Output is correct |
23 |
Correct |
4332 ms |
158784 KB |
Output is correct |
24 |
Correct |
5314 ms |
162032 KB |
Output is correct |
25 |
Correct |
5554 ms |
165320 KB |
Output is correct |
26 |
Correct |
6925 ms |
155568 KB |
Output is correct |
27 |
Correct |
3763 ms |
187724 KB |
Output is correct |
28 |
Correct |
2708 ms |
153276 KB |
Output is correct |
29 |
Correct |
6569 ms |
154408 KB |
Output is correct |
30 |
Correct |
6584 ms |
153820 KB |
Output is correct |
31 |
Correct |
6651 ms |
154384 KB |
Output is correct |
32 |
Correct |
1608 ms |
74968 KB |
Output is correct |
33 |
Correct |
1671 ms |
70276 KB |
Output is correct |
34 |
Correct |
2909 ms |
65660 KB |
Output is correct |
35 |
Correct |
2767 ms |
65576 KB |
Output is correct |
36 |
Correct |
3354 ms |
66536 KB |
Output is correct |
37 |
Correct |
3415 ms |
66432 KB |
Output is correct |