#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];
int isspec[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;
isspec[base[i]] = 0;
}
for(int i = 0; i < fact2.size(); i++)
isspec[fact2[i]] = 1;
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;
if(isspec[node] == 1)
return pqtop.first;
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});
}
}
}
}
return inf;
}
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:80:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int i = 0; i < base.size(); i++) {
| ~~^~~~~~~~~~~~~
factories.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for(int i = 0; i < fact2.size(); i++)
| ~~^~~~~~~~~~~~~~
factories.cpp:88:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 0; i < base.size(); i++) {
| ~~^~~~~~~~~~~~~
factories.cpp:100:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 0; i < fact1.size(); i++) {
| ~~^~~~~~~~~~~~~~
factories.cpp:114: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]
114 | for(int h = 0; h < secg[node].size(); h++) {
| ~~^~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:135:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for(int i = 1; i < base.size(); i++)
| ~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
24684 KB |
Output is correct |
2 |
Correct |
1720 ms |
35052 KB |
Output is correct |
3 |
Correct |
1875 ms |
35096 KB |
Output is correct |
4 |
Correct |
1804 ms |
34972 KB |
Output is correct |
5 |
Correct |
1576 ms |
35180 KB |
Output is correct |
6 |
Correct |
1232 ms |
34924 KB |
Output is correct |
7 |
Correct |
1836 ms |
34924 KB |
Output is correct |
8 |
Correct |
1820 ms |
34924 KB |
Output is correct |
9 |
Correct |
1576 ms |
35056 KB |
Output is correct |
10 |
Correct |
1234 ms |
34772 KB |
Output is correct |
11 |
Correct |
1835 ms |
34796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
24300 KB |
Output is correct |
2 |
Correct |
3344 ms |
124436 KB |
Output is correct |
3 |
Correct |
5690 ms |
128064 KB |
Output is correct |
4 |
Correct |
1934 ms |
124884 KB |
Output is correct |
5 |
Correct |
3510 ms |
161452 KB |
Output is correct |
6 |
Correct |
6014 ms |
129760 KB |
Output is correct |
7 |
Correct |
6171 ms |
54680 KB |
Output is correct |
8 |
Correct |
2288 ms |
54368 KB |
Output is correct |
9 |
Correct |
3793 ms |
59628 KB |
Output is correct |
10 |
Correct |
6133 ms |
55620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
52 ms |
24684 KB |
Output is correct |
2 |
Correct |
1720 ms |
35052 KB |
Output is correct |
3 |
Correct |
1875 ms |
35096 KB |
Output is correct |
4 |
Correct |
1804 ms |
34972 KB |
Output is correct |
5 |
Correct |
1576 ms |
35180 KB |
Output is correct |
6 |
Correct |
1232 ms |
34924 KB |
Output is correct |
7 |
Correct |
1836 ms |
34924 KB |
Output is correct |
8 |
Correct |
1820 ms |
34924 KB |
Output is correct |
9 |
Correct |
1576 ms |
35056 KB |
Output is correct |
10 |
Correct |
1234 ms |
34772 KB |
Output is correct |
11 |
Correct |
1835 ms |
34796 KB |
Output is correct |
12 |
Correct |
21 ms |
24300 KB |
Output is correct |
13 |
Correct |
3344 ms |
124436 KB |
Output is correct |
14 |
Correct |
5690 ms |
128064 KB |
Output is correct |
15 |
Correct |
1934 ms |
124884 KB |
Output is correct |
16 |
Correct |
3510 ms |
161452 KB |
Output is correct |
17 |
Correct |
6014 ms |
129760 KB |
Output is correct |
18 |
Correct |
6171 ms |
54680 KB |
Output is correct |
19 |
Correct |
2288 ms |
54368 KB |
Output is correct |
20 |
Correct |
3793 ms |
59628 KB |
Output is correct |
21 |
Correct |
6133 ms |
55620 KB |
Output is correct |
22 |
Correct |
6757 ms |
137380 KB |
Output is correct |
23 |
Correct |
6472 ms |
136072 KB |
Output is correct |
24 |
Correct |
7038 ms |
141740 KB |
Output is correct |
25 |
Correct |
7205 ms |
148916 KB |
Output is correct |
26 |
Execution timed out |
8090 ms |
139928 KB |
Time limit exceeded |
27 |
Halted |
0 ms |
0 KB |
- |