#include "factories.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <stack>
#include <iostream>
using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))
int const nmax = 500000;
int const lgmax = 20;
ll const inf = 1000000000000000000;
std::vector<std::pair<int,int>> g[1 + nmax];
int far[1 + lgmax][1 + nmax];
int id[1 + nmax], level[1 + nmax];
ll dist[1 + nmax];
void dfs(int node, int parent, int &acc) {
id[node] = ++acc;
for(int h = 0; h < g[node].size(); h++) {
std::pair<int,int> edge = g[node][h];
if(edge.first != parent) {
level[edge.first] = level[node] + 1;
far[0][edge.first] = node;
dist[edge.first] = dist[node] + edge.second;
dfs(edge.first, node, acc);
}
}
}
int lca(int x, int y) {
if(level[x] < level[y])
std::swap(x, y);
for(int h = lgmax; 0 <= h; h--)
if(level[y] + (1 << h) <= level[x])
x = far[h][x];
if(x == y)
return x;
for(int h = lgmax; 0 <= h; h--)
if(far[h][x] != far[h][y]) {
x = far[h][x];
y = far[h][y];
}
return far[0][x];
}
int isanc(int x, int y) {
return lca(x, y) == x;
}
ll getdist(int x, int y) {
return dist[x] + dist[y] - 2 * dist[lca(x, y)];
}
void Init(int N, int A[], int B[], int D[]) {
for(int i = 0; i < N - 1; i++) {
g[A[i]].push_back({B[i], D[i]});
g[B[i]].push_back({A[i], D[i]});
}
int acc = 0;
dfs(0, -1, acc);
for(int h = 1; h <= lgmax; h++)
for(int i = 0;i < N; i++)
far[h][i] = far[h - 1][far[h - 1][i]];
}
bool compare(int x, int y) {
return id[x] < id[y];
}
std::vector<std::pair<int,ll>> secg[1 + nmax];
ll dist1[1 + nmax];
ll solve(std::vector<int> base, std::vector<int> fact1, std::vector<int> fact2) {
for(int i = 0; i < base.size(); i++) {
secg[base[i]].clear();
dist1[base[i]] = inf;
}
std::stack<int> st;
for(int i = 0; i < base.size(); i++) {
while(0 < st.size() && isanc(st.top(), base[i]) == 0)
st.pop();
if(0 < st.size()) {
ll travel = getdist(st.top(), base[i]);
secg[st.top()].push_back({base[i], travel});
secg[base[i]].push_back({st.top(), travel});
}
st.push(base[i]);
}
std::priority_queue<std::pair<ll,int>, std::vector<std::pair<ll,int>>, std::greater<std::pair<ll, int>>> pq;
for(int i = 0; i < fact1.size(); i++) {
dist1[fact1[i]] = 0;
pq.push({0, fact1[i]});
}
while(0 < pq.size()) {
std::pair<ll, int> pqtop = pq.top();
pq.pop();
if(pqtop.first == dist1[pqtop.second]) {
int node = pqtop.second;
for(int h = 0; h < secg[node].size(); h++) {
std::pair<int, ll> edge = secg[node][h];
if(dist1[node] + edge.second < dist1[edge.first]){
dist1[edge.first] = dist1[node] + edge.second;
pq.push({dist1[edge.first], edge.first});
}
}
}
}
ll result = inf;
for(int i = 0; i < fact2.size(); i++)
result = std::min(result, dist1[fact2[i]]);
return result;
}
long long Query(int S, int X[], int T, int Y[]) {
std::vector<int> base;
for(int i = 0; i < S; i++)
base.push_back(X[i]);
for(int i = 0; i < T; i++)
base.push_back(Y[i]);
std::sort(base.begin(), base.end(), compare);
std::vector<int> aux = base;
for(int i = 1; i < base.size(); i++)
aux.push_back(lca(base[i - 1], base[i]));
std::sort(aux.begin(), aux.end(), compare);
aux.erase(std::unique(aux.begin(), aux.end()), aux.end());
std::vector<int> fact1, fact2;
for(int i = 0; i < S; i++)
fact1.push_back(X[i]);
for(int i = 0; i < T; i++)
fact2.push_back(Y[i]);
return solve(aux, fact1, fact2);
}
Compilation message
factories.cpp: In function 'void dfs(int, int, int&)':
factories.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | for(int h = 0; h < g[node].size(); h++) {
| ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'll solve(std::vector<int>, std::vector<int>, std::vector<int>)':
factories.cpp:79:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | for(int i = 0; i < base.size(); i++) {
| ~~^~~~~~~~~~~~~
factories.cpp:84:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for(int i = 0; i < base.size(); i++) {
| ~~^~~~~~~~~~~~~
factories.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < fact1.size(); i++) {
| ~~^~~~~~~~~~~~~~
factories.cpp:107:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int h = 0; h < secg[node].size(); h++) {
| ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:118:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int i = 0; i < fact2.size(); i++)
| ~~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:132:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for(int i = 1; i < base.size(); i++)
| ~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
24684 KB |
Output is correct |
2 |
Correct |
2029 ms |
42952 KB |
Output is correct |
3 |
Correct |
2233 ms |
43064 KB |
Output is correct |
4 |
Correct |
2107 ms |
43136 KB |
Output is correct |
5 |
Correct |
1764 ms |
43060 KB |
Output is correct |
6 |
Correct |
1385 ms |
42860 KB |
Output is correct |
7 |
Correct |
2212 ms |
42704 KB |
Output is correct |
8 |
Correct |
2070 ms |
42984 KB |
Output is correct |
9 |
Correct |
1734 ms |
43368 KB |
Output is correct |
10 |
Correct |
1476 ms |
42952 KB |
Output is correct |
11 |
Correct |
2249 ms |
42540 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
24300 KB |
Output is correct |
2 |
Correct |
3448 ms |
140896 KB |
Output is correct |
3 |
Correct |
6043 ms |
143936 KB |
Output is correct |
4 |
Correct |
1994 ms |
141012 KB |
Output is correct |
5 |
Correct |
3659 ms |
178084 KB |
Output is correct |
6 |
Correct |
6385 ms |
146208 KB |
Output is correct |
7 |
Correct |
6864 ms |
67112 KB |
Output is correct |
8 |
Correct |
2389 ms |
67072 KB |
Output is correct |
9 |
Correct |
3752 ms |
72472 KB |
Output is correct |
10 |
Correct |
6299 ms |
68852 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
55 ms |
24684 KB |
Output is correct |
2 |
Correct |
2029 ms |
42952 KB |
Output is correct |
3 |
Correct |
2233 ms |
43064 KB |
Output is correct |
4 |
Correct |
2107 ms |
43136 KB |
Output is correct |
5 |
Correct |
1764 ms |
43060 KB |
Output is correct |
6 |
Correct |
1385 ms |
42860 KB |
Output is correct |
7 |
Correct |
2212 ms |
42704 KB |
Output is correct |
8 |
Correct |
2070 ms |
42984 KB |
Output is correct |
9 |
Correct |
1734 ms |
43368 KB |
Output is correct |
10 |
Correct |
1476 ms |
42952 KB |
Output is correct |
11 |
Correct |
2249 ms |
42540 KB |
Output is correct |
12 |
Correct |
20 ms |
24300 KB |
Output is correct |
13 |
Correct |
3448 ms |
140896 KB |
Output is correct |
14 |
Correct |
6043 ms |
143936 KB |
Output is correct |
15 |
Correct |
1994 ms |
141012 KB |
Output is correct |
16 |
Correct |
3659 ms |
178084 KB |
Output is correct |
17 |
Correct |
6385 ms |
146208 KB |
Output is correct |
18 |
Correct |
6864 ms |
67112 KB |
Output is correct |
19 |
Correct |
2389 ms |
67072 KB |
Output is correct |
20 |
Correct |
3752 ms |
72472 KB |
Output is correct |
21 |
Correct |
6299 ms |
68852 KB |
Output is correct |
22 |
Correct |
7892 ms |
150456 KB |
Output is correct |
23 |
Correct |
6999 ms |
141072 KB |
Output is correct |
24 |
Execution timed out |
8019 ms |
146872 KB |
Time limit exceeded |
25 |
Halted |
0 ms |
0 KB |
- |