#include "factories.h"
#include <bits/stdc++.h>
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define ll long long
#define endl '\n'
using namespace std;
vector<ii> w[500005];
vector<pair<int,ll> > w2[500005];
int level[500005][33];
int First[500005];
int End[500005];
ll dist[500005];
int DFStime;
int color[500005];
int s[500005];
int t[500005];
ll mindist;
void DFS(int u,int par)
{
First[u] = ++DFStime;
level[u][0] = par;
for(int i = 1;i < 33;i++)
{
level[u][i] = level[level[u][i - 1]][i - 1];
}
for(auto v:w[u])
{
if(v.first == par)
{
continue;
}
dist[v.first] = dist[u] + v.second;
DFS(v.first,u);
}
End[u] = DFStime;
}
bool check(int u,int v)
{
return (First[u] <= First[v] and End[v] <= End[u]);
}
int LCA(int u,int v)
{
if(check(u,v))
{
return u;
}
if(check(v,u))
{
return v;
}
for(int i = 32;i >= 0;i--)
{
if(!check(level[u][i],v))
{
u = level[u][i];
}
}
return level[u][0];
}
void Init(int n, int a[], int b[], int d[])
{
for(int i = 0;i < n - 1;i++)
{
w[a[i]].pb({b[i],d[i]}),
w[b[i]].pb({a[i],d[i]});
}
DFS(0,0);
}
void edge(int u,int v)
{
if(u == v)
{
return;
}
ll d = abs(dist[u] - dist[v]);
w2[u].push_back({v,d});
w2[v].push_back({u,d});
}
int virtual_tree(vector<int> &nodes)
{
sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (First[i] < First[j]);});
for(int i = (int) (nodes.size()) - 2;i >= 0;i--)
{
int res = LCA(nodes[i],nodes[i + 1]);
nodes.push_back(res);
}
sort(nodes.begin(),nodes.end(),[](int &i, int &j){return (First[i] < First[j]);});
vector<int> s;
s.push_back(nodes[0]);
for(int i = 1;i < nodes.size();i++)
{
while(!check(s.back(),nodes[i]))
{
edge(s.back(),s[s.size() - 2]);
s.pop_back();
}
s.push_back(nodes[i]);
}
while(s.size() > 1)
{
edge(s.back(),s[s.size() - 2]);
s.pop_back();
}
return s[0];
}
ii DFS2(int u,int par)
{
ll min1 = 1e18;
ll min2 = 1e18;
if(color[u] == 1)
{
min1 = 0;
}
else if(color[u] == 2)
{
min2 = 0;
}
for(auto v:w2[u])
{
if(v.first != par)
{
ii tree = DFS2(v.first,u);
min1 = min(min1,v.second + tree.first);
min2 = min(min2,v.second + tree.second);
}
}
mindist = min(mindist,min1 + min2);
return {min1,min2};
}
long long Query(int n, int x[], int m, int y[])
{
vector<int> nodes;
for(int i = 0;i < n;i++)
{
nodes.push_back(x[i]);
color[x[i]] = 1;
}
for(int i = 0;i < n;i++)
{
nodes.push_back(y[i]);
color[y[i]] = 2;
}
int r = virtual_tree(nodes);
mindist = 1e18;
DFS2(r,r);
for(auto x:nodes)
w2[x].clear(),
color[x] = 0;
return mindist;
}
Compilation message
factories.cpp: In function 'int virtual_tree(std::vector<int>&)':
factories.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i = 1;i < nodes.size();i++)
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
24148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
14 ms |
24020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
29 ms |
24148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
