#include <bits/stdc++.h>
#include "factories.h"
#define int long long
//#include "grader.cpp"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<pii> > g;
vector<bool> vis;
vector<int> s;
vector<vector<ll> > d;
vector<vector<int> > pa;
vector<ll> mini;
void calc(int v, int p)
{
s[v] = 1;
for(auto [x, w] : g[v])
{
if(vis[x]) continue;
if(x == p) continue;
calc(x, v);
s[v] += s[x];
}
}
int findc(int v, int p, int bp)
{
for(auto [x, w] : g[v])
{
if(x == p || vis[x]) continue;
if(s[bp] / 2 < s[x]) return findc(x, v, bp);
}
return v;
}
void calc2(int v, int p, ll dep, int l, int bp)
{
pa[v][l] = bp;
d[v][l] = dep;
for(auto [x, w] : g[v])
{
if(x == p || vis[x]) continue;
calc2(x, v, dep + w, l, bp);
}
}
void dec(int v, int l)
{
calc(v, 0);
int c = findc(v, 0, v);
vis[c] = 1;
calc2(c, 0, 0, l, c);
for(auto [x, w] : g[c])
{
if(!vis[x]) dec(x, l + 1);
}
}
ll Query(int t, int b[], int s, int a[])
{
vector<int> ve;
for(int i = 0; i < s; i++)
{
int x = a[i];
for(int j = 0; j < 20; j++)
{
int v = pa[x][j];
if(v != 0)
{
mini[v] = min(mini[v], d[x][j]);
ve.push_back(v);
}
}
}
ll ans = 1e15;
for(int i = 0; i < t; i++)
{
int x = b[i];
ll act = 1e15;
for(int j = 0; j < 20; j++)
{
int v = pa[x][j];
if(v != 0)
{
act = min(act, mini[v] + d[x][j]);
}
}
ans = min(act, ans);
}
for(auto x : ve) mini[x] = 1e15;
return ans;
}
void Init(int n, int a[], int b[], int c[])
{
ios::sync_with_stdio(0);
cin.tie(0);
/*int n, q;
cin >> n >> q;*/
g.resize(n);
vis.resize(n);
s.resize(n);
d.resize(n, vector<ll>(20));
pa.resize(n, vector<int>(20));
mini.resize(n, 1e15);
for(int i = 0; i < n - 1; i++)
{
int x = a[i], y = b[i], w = c[i];
/*int x, y, w;
cin >> x >> y >> w;*/
g[x].push_back({y, w});
g[y].push_back({x, w});
}
dec(1, 0);
/*while(q--)
{
int s, t;
cin >> s >> t;
int a[s], b[t];
for(int i = 0; i < s; i++) cin >> a[i];
for(int i = 0; i < t; i++) cin >> b[i];
cout << Query(s, a, t, b) << "\n";
}*/
}
Compilation message
factories.cpp: In function 'void calc(long long int, long long int)':
factories.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
17 | for(auto [x, w] : g[v])
| ^
factories.cpp: In function 'long long int findc(long long int, long long int, long long int)':
factories.cpp:28:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
28 | for(auto [x, w] : g[v])
| ^
factories.cpp: In function 'void calc2(long long int, long long int, ll, long long int, long long int)':
factories.cpp:39:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
39 | for(auto [x, w] : g[v])
| ^
factories.cpp: In function 'void dec(long long int, long long int)':
factories.cpp:53:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
53 | for(auto [x, w] : g[c])
| ^
/usr/bin/ld: /tmp/cc3oShYc.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
