This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the Name of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pp pop_back
#define all(x) x.begin(), x.end()
#define cln(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define unq(a, n); {vector<int> v; for(int i = 0; i < n; i++) v.pb(a[i]); cln(v); for (int i = 0; i < n; i++) a[i] = lower_bound(all(v), a[i]) - v.begin();}
const int N = 5e5 + 12, inf = 1e18 + 12;
vector<pii> g[N];
int sz[N], val[N], cpar[N], q, n;
set<pii> cdis[N];
bool mrk[N];
void dfs(int u, int par = -1) {
sz[u] = 1;
for (auto i: g[u])
if (i.F != par && !mrk[i.F]) {
dfs(i.F, u);
sz[u] += sz[i.F];
}
}
int find_centroid(int u, int c, int par = -1) {
for (auto i: g[u])
if (!mrk[i.F] && i.F != par && sz[i.F] > (c - 1) / 2)
return find_centroid(i.F, c, u);
return u;
}
void fill_cdis(int u, int cent, int c = 0, int par = -1) {
cdis[cent].insert({u, c});
for (auto i: g[u])
if (!mrk[i.F] && i.F != par)
fill_cdis(i.F, cent, c + i.S, u);
}
void decompose(int u, int par = -1) {
dfs(u);
u = find_centroid(u, sz[u]);
fill_cdis(u, u);
cpar[u] = par;
mrk[u] = true;
for (auto i: g[u])
if (!mrk[i.F])
decompose(i.F, u);
}
void Init(int c, int a[], int b[], int d[]) {
n = c;
for (int i = 1; i < n; i++) {
g[a[i]].pb({b[i], d[i]});
g[b[i]].pb({a[i], d[i]});
}
decompose(0);
fill(val, val + n, inf);
}
void add(int u, int v) {
if (u == -1)
return;
val[u] = min(val[u], cdis[u].lower_bound({v, -1})->S);
add(cpar[u], v);
}
int ask(int u, int v) {
if (u == -1)
return inf;
int tmp = cdis[u].lower_bound({v, -1})->S;
return min(ask(cpar[u], v), tmp + val[u]);
}
void rem(int u) {
val[u] = inf;
if (cpar[u] != -1)
rem(cpar[u]);
}
int Query(int s, int x[], int t, int y[]) {
for (auto i: x)
add(i, i);
int res = inf;
for (auto i: y)
res = min(res, ask(i, i));
for (auto i: x)
rem(i);
return res;
}
Compilation message (stderr)
factories.cpp: In function 'long long int Query(long long int, long long int*, long long int, long long int*)':
factories.cpp:87:15: error: 'begin' was not declared in this scope
87 | for (auto i: x)
| ^
factories.cpp:87:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note: 'std::filesystem::__cxx11::begin'
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
factories.cpp:87:15: error: 'end' was not declared in this scope
87 | for (auto i: x)
| ^
factories.cpp:87:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note: 'std::end'
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note: 'std::filesystem::__cxx11::end'
554 | end(recursive_directory_iterator) noexcept
| ^~~
factories.cpp:90:15: error: 'begin' was not declared in this scope
90 | for (auto i: y)
| ^
factories.cpp:90:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note: 'std::filesystem::__cxx11::begin'
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
factories.cpp:90:15: error: 'end' was not declared in this scope
90 | for (auto i: y)
| ^
factories.cpp:90:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note: 'std::end'
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note: 'std::filesystem::__cxx11::end'
554 | end(recursive_directory_iterator) noexcept
| ^~~
factories.cpp:92:15: error: 'begin' was not declared in this scope
92 | for (auto i: x)
| ^
factories.cpp:92:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from factories.cpp:3:
/usr/include/c++/10/valarray:1224:5: note: 'std::begin'
1224 | begin(const valarray<_Tp>& __va)
| ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:549:3: note: 'std::filesystem::__cxx11::begin'
549 | begin(recursive_directory_iterator __iter) noexcept
| ^~~~~
factories.cpp:92:15: error: 'end' was not declared in this scope
92 | for (auto i: x)
| ^
factories.cpp:92:15: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
from factories.cpp:3:
/usr/include/c++/10/valarray:1244:5: note: 'std::end'
1244 | end(const valarray<_Tp>& __va)
| ^~~
In file included from /usr/include/c++/10/filesystem:46,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from factories.cpp:3:
/usr/include/c++/10/bits/fs_dir.h:554:3: note: 'std::filesystem::__cxx11::end'
554 | end(recursive_directory_iterator) noexcept
| ^~~