#include "factories.h"
#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <algorithm>
#include <stack>
#include <functional>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
const int log_height = 20;
typedef vector<ll> vi;
typedef pair<ll, int> ii;
typedef vector<ii> vii;
vector<vii> adj_list, up;
vi tin, tout, dist, depth;
vii euler_tour;
int graph_sz, n_q = 0;
vi color;
int lg(unsigned long long i)
{
return i ? __builtin_clzll(1) - __builtin_clzll(i) : -1;
}
void get_euler_tour(int node, int par)
{
tin[node] = euler_tour.size();
euler_tour.push_back({depth[node], node});
for (ii edge : adj_list[node])
{
if (edge.second == par)
continue;
depth[edge.second] = depth[node] + 1;
dist[edge.second] = dist[node] + edge.first;
get_euler_tour(edge.second, node);
euler_tour.push_back({depth[node], node});
}
tout[node] = euler_tour.size() - 1;
}
void Init(int n, int u[], int v[], ll w[])
{
adj_list.assign(n, vii());
graph_sz = n;
for (int i = 0; i < n - 1; i++)
{
adj_list[u[i]].push_back({w[i], v[i]});
adj_list[v[i]].push_back({w[i], u[i]});
}
tin.assign(n, -1);
tout.assign(n, -1);
depth.assign(n, 0);
dist.assign(n, 0);
color.assign(n, 0);
get_euler_tour(0, -1);
up.assign(euler_tour.size(), vii(log_height));
for (int i = 0; i < euler_tour.size(); i++)
{
up[i][0] = euler_tour[i];
}
for (int i = 1; i < log_height; i++)
{
for (int j = 0; j < euler_tour.size(); j++)
{
up[j][i] = up[j][i - 1];
if (j + (1 << (i - 1)) < euler_tour.size())
{
up[j][i] = min(up[j][i], up[j + (1 << (i - 1))][i - 1]);
}
}
}
}
ii rmq(int l, int r)
{
int lvl = lg(r - l + 1);
return min(up[l][lvl], up[r - (1 << lvl) + 1][lvl]);
}
int get_lca(int u, int v)
{
if (tin[u] > tin[v])
swap(u, v);
ii rmq_node = rmq(tin[u], tin[v]);
return rmq_node.second;
}
bool comp(int u, int v)
{
return tin[u] < tin[v];
}
ll query(int s, int x[], int t, int y[])
{
vi node;
for (int i = 0; i < s; i++)
{
node.push_back(x[i]);
color[x[i]] = 3 * n_q + 1;
}
for (int i = 0; i < t; i++)
{
node.push_back(y[i]);
color[y[i]] = 3 * n_q + 2;
}
sort(node.begin(), node.end(), comp);
for (int i = 1; i < s + t; i++)
{
int adj_lca = get_lca(node[i], node[i - 1]);
if (color[adj_lca] <= 3 * n_q)
{
node.push_back(adj_lca);
color[adj_lca] = 3 * n_q + 3;
}
}
int n = node.size();
vector<vii> adj_list1(n);
stack<ii> st;
for (int i = 0; i < n; i++)
{
int id = node[i];
while (!st.empty() && get_lca(st.top().first, id) != st.top().first)
{
st.pop();
}
if (!st.empty())
{
adj_list1[st.top().second].push_back({dist[st.top().first] - dist[id], i});
}
st.push({id, i});
}
vector<vi> dp(n, vi(3, LLONG_MAX / 2));
std::function<void(int)> dfs = [&](int u)
{
dp[u][color[node[u]] % 3] = 0;
for (ii edge : adj_list1[u])
{
dfs(edge.second);
for (int i = 0; i < 3; i++)
{
dp[u][i] = min(dp[u][i], dp[edge.second][i] + edge.first);
}
}
};
dfs(0);
ll min_dist = LLONG_MAX;
for (int i = 0; i < n; i++)
{
if (color[node[i]] % 3 == 0)
continue;
min_dist = min(min_dist, dp[i][3 - (color[node[i]] % 3)]);
}
n_q++;
return min_dist;
}
Compilation message
factories.cpp: In function 'void Init(int, int*, int*, long long int*)':
factories.cpp:63:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for (int i = 0; i < euler_tour.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:69:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | for (int j = 0; j < euler_tour.size(); j++)
| ~~^~~~~~~~~~~~~~~~~~~
factories.cpp:72:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | if (j + (1 << (i - 1)) < euler_tour.size())
| ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc5J8tGa.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status
