#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
#include "factories.h"
using namespace std;
int f[100005], ff[100005], a[100005], b[100005];
vector<pair<int, int>> g[100005], c[100005];
int vt[100005], in[100005], out[100005], cc[100005], h[100005], dd[100005], p[100005][21], t = 0;
bool cmp(int x, int y) {
return in[x] < in[y];
}
void dfs(int u, int x) {
t++;
in[u] = t;
p[u][0] = x;
for (int i = 1; i <= 20; i++) {
p[u][i] = p[p[u][i - 1]][i - 1];
}
for (auto w : g[u]) {
int v = w.first, k = w.second;
if (v != x) {
h[v] = h[u] + 1;
dd[v] = dd[u] + k;
dfs(v, u);
}
}
out[u] = t;
}
void dfs1(int u, int x) {
f[u] = a[u] = b[u] = 999999999;
for (auto w : c[u]) {
int v = w.first, k = w.second;
dfs1(v, u);
f[u] = min(f[v] + k, f[u]);
if (f[v] + k <= a[u]) {
b[u] = a[u];
a[u] = f[v] + k;
}
else if (f[v] + k <= b[u]) {
b[u] = f[v] + k;
}
}
if (vt[u] >= 2) f[u] = 0;
}
void dfs2(int u, int x, int y) {
ff[u] = 999999999;
if (vt[u] >= 2) ff[u] = 0;
else {
if (x != -1) {
if (vt[x] >= 2) ff[u] = y;
else {
if (f[u] + y == a[x]) ff[u] = b[x] + y;
else ff[u] = a[x] + y;
ff[u] = min(ff[u], ff[x] + y);
}
}
}
for (auto w : c[u]) {
int v = w.first, x = w.second;
dfs2(v, u, x);
}
}
int LCA(int u, int v) {
if (h[u] < h[v]) swap(u, v);
int lg = log2(h[u]) + 1;
for (int i = lg; i >= 0; i--) {
if (h[p[u][i]] >= h[v]) {
u = p[u][i];
}
}
if (u == v) return u;
for (int i = lg; i >= 0; i--) {
if (p[u][i] != p[v][i]) {
u = p[u][i];
v = p[v][i];
}
}
return p[u][0];
}
int trya(int u, int v) {
return dd[u] + dd[v] - dd[LCA(u, v)] * 2;
}
bool check(int x, int y) {
return (in[x] <= in[y]) && (out[y] <= out[x]);
}
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]});
}
dfs(1, 1);
}
long long Query(int s, int x[], int t, int y[]) {
vector<int> v;
for (int i = 0; i < s; i++) {
v.push_back(x[i]);
vt[x[i]]++;
}
for (int i = 0; i < t; i++) {
v.push_back(y[i]);
vt[y[i]] += 2;
}
sort(v.begin(), v.end(), cmp);
int k = v.size();
for (int i = 1; i < k; i++) {
int g = LCA(v[i], v[i - 1]);
v.push_back(g);
}
sort(v.begin(), v.end(), cmp);
stack<int> st;
for (int i = 0; i < v.size(); i++) {
if (cc[v[i]] == 0) {
while (!st.empty() && (!check(st.top(), v[i]))) {
st.pop();
}
if (!st.empty()) {
c[st.top()].push_back({v[i], trya(st.top(), v[i])});
}
st.push(v[i]);
cc[v[i]] = 1;
}
}
dfs1(v[0], -1);
dfs2(v[0], -1, -1);
int res = 999999999;
for (int i = 0; i < v.size(); i++) {
if (vt[v[i]] == 1 || vt[v[i]] == 2 || vt[v[i]] == 3) {
res = min(res, min(f[v[i]], ff[v[i]]));
}
}
for (int i = 0; i < v.size(); i++) {
cc[v[i]] = 0;
c[v[i]].clear();
vt[v[i]] = 0;
}
return res;
}
Compilation message
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
factories.cpp:128:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
128 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
factories.cpp:133:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
133 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
5204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
5332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
