#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <stack>
//#include "factories.h"
using namespace std;
const int N=100005;
const long long inf=1e18+7;
long long dp[N], dp1[N];
int a[N], b[N];
vector<pair<int, int>> g[N], c[N];
int vt[N], in[N], out[N], cc[N], h[N], dd[N], p[N][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 compute_dp(int x){
if(vt[x]&1){
dp[x]=0;
}
else{
dp[x]=inf;
}
if(vt[x]&2){
dp1[x]=0;
}
else{
dp1[x]=inf;
}
for(int i=0;i<c[x].size();i++){
compute_dp(c[x][i].first);
dp[x]=min(dp[x],dp[c[x][i].first]+c[x][i].second);
dp1[x]=min(dp1[x],dp1[c[x][i].first]+c[x][i].second);
//cout<<x<<' '<<c[x][i].first<<' '<<dp[x]<<' '<<dp[c[x][i].first]+c[x][i].second<<' '<<dp1[x]<<' '<<dp1[c[x][i].first]+c[x][i].second<<endl;
}
}
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(0, 0);
}
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);
vector<int> st;
//cout<<in[0]<<' '<<in[1]<<endl;
for (int i = 0; i < v.size(); i++) {
if (cc[v[i]] == 0) {
while (st.size() && (!check(st.back(), v[i]))) {
st.pop_back();
}
if (st.size()) {
c[st.back()].push_back({v[i], trya(st.back(), v[i])});
//cout<<st.back()<<' '<<v[i]<<' '<<trya(st.back(), v[i])<<endl;
}
st.push_back(v[i]);
cc[v[i]] = 1;
}
}
long long res = inf;
compute_dp(v[0]);
for (int i = 0; i < v.size(); i++) {
res=min(res,dp[v[i]]+dp1[v[i]]);
//cout<<v[i]<<' '<<dp[v[i]]<<' '<<dp1[v[i]]<<" dp value"<<endl;
}
for (int i = 0; i < v.size(); i++) {
cc[v[i]] = 0;
c[v[i]].clear();
vt[v[i]] = 0;
}
return res;
}
/*
signed main(){
int a[]={0,1,2,2,4,1},b[]={1,2,3,4,5,6},d[]={4,4,5,6,5,3};
Init(7,a,b,d);
int e[]={0,6},f[]={3,4};
cout<<Query(2,e,2,f)<<endl;
int g[]={0,1,3},h[]={4,6};
cout<<Query(3,g,2,h)<<endl;
int i[]={2},j[]={5};
cout<<Query(1,i,1,j)<<endl;
}
*/
Compilation message
factories.cpp: In function 'void compute_dp(int)':
factories.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<c[x].size();i++){
| ~^~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
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 < v.size(); i++) {
| ~~^~~~~~~~~~
factories.cpp:118:23: 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 < v.size(); i++) {
| ~~^~~~~~~~~~
factories.cpp:122:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for (int i = 0; i < v.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
1037 ms |
13980 KB |
Output is correct |
| 3 |
Correct |
1194 ms |
23552 KB |
Output is correct |
| 4 |
Incorrect |
1137 ms |
23512 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 2 |
Runtime error |
256 ms |
32404 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
5332 KB |
Output is correct |
| 2 |
Correct |
1037 ms |
13980 KB |
Output is correct |
| 3 |
Correct |
1194 ms |
23552 KB |
Output is correct |
| 4 |
Incorrect |
1137 ms |
23512 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
