#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<int> ad[500001], c[500001], ad2[500001], c2[500001];
int n, type[500001], tin[500001], tout[500001], sparse[20][1000002], h[500001], dis[500001], lg2[1000003], appear[500001], ganl[500001], ganr[500001], dfsc = 0, cur = 0;
bool visited[500001];
void dfs(int u)
{
tin[u] = ++dfsc;
visited[u] = 1;
sparse[0][++cur] = u;
appear[u] = cur;
for(int i = 0; i < ad[u].size(); i++) if(visited[ad[u][i]] == 0){
int v = ad[u][i];
h[v] = h[u] + 1;
dis[v] = dis[u] + c[u][i];
dfs(v);
sparse[0][++cur] = u;
}
tout[u] = dfsc;
}
void preprocess()
{
for(int i = 1; i < 20; i++){
for(int j = 1; j + (1 << (i-1)) <= cur; j++){
int k = j + (1 << (i-1));
if(h[sparse[i-1][j]] < h[sparse[i-1][k]]) sparse[i][j] = sparse[i-1][j];
else sparse[i][j] = sparse[i-1][k];
//cout<<i<<" "<<j<<" "<<sparse[i][j]<<endl;
}
}
}
int lca(int u, int v)
{
int l = appear[u], r = appear[v];
if(l > r) swap(l, r);
int x = lg2[r-l+1];
if(h[sparse[x][l]] < h[sparse[x][r-(1 << x)+1]]) return sparse[x][l];
else return sparse[x][r-(1 << x)+1];
}
bool cmp(int u, int v)
{
return tin[u] < tin[v];
}
bool ancestor(int u, int v)
{
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
void Init(int N, int a[], int b[], int d[])
{
n = N;
for(int i = 0; i < n; i++){a[i]++; b[i]++;}
for(int i = 0; i < n-1; i++){
ad[a[i]].push_back(b[i]);
ad[b[i]].push_back(a[i]);
c[a[i]].push_back(d[i]);
c[b[i]].push_back(d[i]);
}
h[0] = 1e9;
dfs(1);
preprocess();
for(int i = 2; i <= 2*n; i++){
if((1 << lg2[i-1])*2 > i) lg2[i] = lg2[i-1];
else lg2[i] = lg2[i-1]+1;
}
for(int i = 1; i <= n; i++){
visited[i] = 0; ganl[i] = 1e9; ganr[i] = 1e9;
}
}
void dfsdp(int u)
{
visited[u] = 1;
ganl[u] = 1e9; ganr[u] = 1e9;
if(type[u] == 1) ganl[u] = 0;
if(type[u] == 2) ganr[u] = 0;
for(int i = 0; i < ad2[u].size(); i++) if(visited[ad2[u][i]] == 0){
int v = ad2[u][i];
dfsdp(v);
ganl[u] = min(ganl[u], ganl[v] + c2[u][i]);
ganr[u] = min(ganr[u], ganr[v] + c2[u][i]);
}
visited[u] = 0;
}
void dfsreroot(int u, int par, int cost)
{
if(par > 0){
ganl[u] = min(ganl[u], ganl[par] + cost);
ganr[u] = min(ganr[u], ganr[par] + cost);
}
for(int i = 0; i < ad2[u].size(); i++) if(ad2[u][i] != par){
int v = ad2[u][i];
dfsreroot(v, u, c2[u][i]);
}
}
long long Query(int s, int x[], int t, int y[])
{
vector<int> st; //build virtual tree
for(int i = 0; i < s; i++){
x[i]++;
st.push_back(x[i]);
type[x[i]] = 1;
}
for(int i = 0; i < t; i++){
y[i]++;
st.push_back(y[i]);
type[y[i]] = 2;
}
sort(st.begin(), st.end(), cmp);
for(int i = 0; i < s+t-1; i++){
int node = lca(st[i], st[i+1]);
if(node != st[i] && node != st[i+1]) st.push_back(node);
}
sort(st.begin(), st.end(), cmp);
stack<int> wtf;
int bruh = 0;
for(int u : st){
while(wtf.size() > 0 && ancestor(wtf.top(), u) == 0) wtf.pop();
if(wtf.size() > 0){
ad2[u].push_back(wtf.top());
ad2[wtf.top()].push_back(u);
c2[u].push_back(dis[u] - dis[wtf.top()]);
c2[wtf.top()].push_back(dis[u] - dis[wtf.top()]);
bruh++;
}
wtf.push(u);
}
int root = st[0];
dfsdp(root);
dfsreroot(root, 0, 0);
long long ans = 1e9;
for(int u : st){
ans = min(ans, (long long)ganl[u] + ganr[u]);
type[u] = 0; ad2[u].clear(); c2[u].clear(); ganl[u] = 1e9; ganr[u] = 1e9;
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, q;
cin>>n>>q;
int u[n-1], v[n-1], cost[n-1];
for(int i = 0; i < n-1; i++) cin>>u[i]>>v[i]>>cost[i];
Init(n, u, v, cost);
for(int test = 0; test < q; test++){
int a, b;
cin>>a>>b;
int l[a], r[b];
for(int i = 0; i < a; i++) cin>>l[i];
for(int i = 0; i < b; i++) cin>>r[i];
cout<<Query(a, l, b, r)<<'\n';
}
}
*/
Compilation message
factories.cpp: In function 'void dfs(int)':
factories.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i = 0; i < ad[u].size(); i++) if(visited[ad[u][i]] == 0){
| ~~^~~~~~~~~~~~~~
factories.cpp: In function 'void dfsdp(int)':
factories.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
76 | for(int i = 0; i < ad2[u].size(); i++) if(visited[ad2[u][i]] == 0){
| ~~^~~~~~~~~~~~~~~
factories.cpp: In function 'void dfsreroot(int, int, int)':
factories.cpp:90:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int i = 0; i < ad2[u].size(); i++) if(ad2[u][i] != par){
| ~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
457 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
392 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
457 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
