#include "factories.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
long long n, dist[500010], depth[500010], ord[500010], p[500010][20], cnt, dp[500010], node[500010], par[500010], lst, minn;
vector<pair<long long,long long>> edge[500010], nodes, stack;
vector<int> stk, hv, adj[500010];
void dfs1(int u, int v, long long _dist, int _depth) {
dist[u] = _dist;
depth[u] = _depth;
p[u][0] = v;
ord[u] = ++cnt;
for (int i = 1; i < 20; i++) p[u][i] = p[p[u][i-1]][i-1];
for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs1(edge[u][i].f,u,_dist+edge[u][i].s,_depth+1);
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for (int i = 0; i < n-1; i++) {
edge[A[i]+1].push_back({B[i]+1,D[i]});
edge[B[i]+1].push_back({A[i]+1,D[i]});
}
for (int i = 0; i <= n; i++) dp[i] = 1e18;
dfs1(1,0,0,1);
}
int lca(int u, int v) {
if (depth[u] > depth[v]) swap(u,v);
int i = 19;
while (i >= 0) {
if (depth[p[v][i]] >= depth[u]) v = p[v][i];
i--;
}
if (u == v) return u;
i = 19;
while (i >= 0) {
if (p[v][i] != p[u][i]) v = p[v][i], u = p[u][i];
i--;
}
return p[u][0];
}
void dfs2(int u) {
if (node[u] == 1) dp[u] = dist[u];
for (int i = 0; i < adj[u].size(); i++) {
dfs2(adj[u][i]);
dp[u] = min(dp[u],dp[adj[u][i]]);
}
}
void dfs3(int u) {
dp[u] = (long long)1e18-dp[u];
for (int i = 0; i < adj[u].size(); i++) dfs3(adj[u][i]);
}
void dfs4(int u) {
if (node[u] == 2) minn = min(minn,(long long)1e18-stack.back().f+dist[u]-2*dist[stack.back().s]);
for (int i = 0; i < adj[u].size(); i++) {
if (stack.back().f <= dp[adj[u][i]]) stack.push_back({dp[adj[u][i]],adj[u][i]});
else stack.push_back(stack.back());
dfs4(adj[u][i]);
stack.pop_back();
}
}
long long Query(int S, int X[], int T, int Y[]) {
minn = 1e18;
for (int i = 0; i < S; i++) {
node[X[i]+1] = 1;
nodes.push_back({ord[X[i]+1],X[i]+1});
}
for (int i = 0; i < T; i++) {
node[Y[i]+1] = 2;
nodes.push_back({ord[Y[i]+1],Y[i]+1});
}
sort(nodes.begin(),nodes.end());
for (int i = 0; i < nodes.size(); i++) {
if (stk.size()) {
int u = lca(nodes[i].s,stk.back());
while (stk.size() && (lca(u,stk.back()) == u)) {
lst = stk.back();
hv.push_back(lst);
stk.pop_back();
if (stk.size()) par[lst] = stk.back();
}
if (lst == u) hv.pop_back();
else par[lst] = u;
stk.push_back(u);
}
stk.push_back(nodes[i].s);
}
while (stk.size()) {
lst = stk.back();
stk.pop_back();
hv.push_back(lst);
if (stk.size()) par[lst] = stk.back();
}
for (int i = 0; i < hv.size(); i++) adj[par[hv[i]]].push_back(hv[i]);
dfs2(0);
dfs3(0);
stack.push_back({dp[0],0});
dfs4(0);
for (int i = 0; i < S; i++) node[X[i]+1] = 0;
for (int i = 0; i < T; i++) node[Y[i]+1] = 0;
for (int i = 0; i < hv.size(); i++) dp[hv[i]] = 1e18, par[hv[i]] = 0, adj[hv[i]].clear();
adj[0].clear();
dp[0] = 1e18;
nodes.clear();
hv.clear();
stk.clear();
stack.clear();
return minn;
}
Compilation message
factories.cpp: In function 'void dfs1(int, int, long long int, int)':
factories.cpp:19:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int i = 0; i < edge[u].size(); i++) if (edge[u][i].f != v) dfs1(edge[u][i].f,u,_dist+edge[u][i].s,_depth+1);
| ~~^~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs2(int)':
factories.cpp:50:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs3(int)':
factories.cpp:58:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for (int i = 0; i < adj[u].size(); i++) dfs3(adj[u][i]);
| ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs4(int)':
factories.cpp:63:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < adj[u].size(); i++) {
| ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:82:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int i = 0; i < nodes.size(); i++) {
| ~~^~~~~~~~~~~~~~
factories.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 0; i < hv.size(); i++) adj[par[hv[i]]].push_back(hv[i]);
| ~~^~~~~~~~~~~
factories.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int i = 0; i < hv.size(); i++) dp[hv[i]] = 1e18, par[hv[i]] = 0, adj[hv[i]].clear();
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
53848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
53848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
53848 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
