| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 591556 | Do_you_copy | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
using ull = unsigned ll;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());
ll min(const ll &a, const ll &b){
return (a < b) ? a : b;
}
ll max(const ll &a, const ll &b){
return (a > b) ? a : b;
}
//const ll Mod = 1000000009;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 5e5 + 2;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int n, q;
int a[maxN], b[maxN];
int par[maxN];
int depth[maxN];
int subtree_size[maxN];
ll dist[maxN][20];
ll ans[maxN];
bool visited[maxN];
vector <pii> adj[maxN];
void centroid_dfs(int u, int p){
subtree_size[u] = 1;
for (const auto &i: adj[u]){
if (visited[i.fi] || i.fi == p) continue;
centroid_dfs(i.fi, u);
subtree_size[u] += subtree_size[i.fi];
}
}
int find_centroid(int u, int p, int sz){
for (const auto &i: adj[u]){
if (visited[i.fi] || i.fi == p) continue;
if (subtree_size[i.fi] > sz / 2) return find_centroid(i.fi, u, sz);
}
return u;
}
void find_distance(int u, int p, int c, ll d = 0){
for (const auto &i: adj[u]){
if (visited[i.fi] || i.fi == p) continue;
dist[i.fi][c] = d + i.se;
find_distance(i.fi, u, c, d + i.se);
}
}
void update(int u){
int v = u;
while (v){
ans[v] = min(ans[v], dist[u][depth[v]]);
v = par[v];
}
}
ll get(int u){
ll res = inf;
int v = u;
while (v){
res = min(res, ans[v] + dist[u][depth[v]]);
v = par[v];
}
return res;
}
void reupdate(int u){
int v = u;
while (v){
ans[u] = inf;
v = par[v];
}
}
int build_centroid(int u, int low){
centroid_dfs(u, -1);
int centroid = find_centroid(u, -1, subtree_size[u]);
visited[centroid] = 1;
depth[centroid] = low;
find_distance(centroid, -1, low);
for (const auto &i: adj[centroid]){
if (visited[i.fi]) continue;
par[build_centroid(i.fi, low + 1)] = centroid;
}
return centroid;
}
void Init(){
cin >> n >> q;
memset(ans, 0x3f, sizeof(ans));
for (int i = 1; i < n; ++i){
int u, v, w;
cin >> u >> v >> w;
adj[u + 1].pb({v + 1, w});
adj[v + 1].pb({u + 1, w});
}
par[build_centroid(1, 1)] = 0;
while (q--){
int s, t;
cin >> s >> t;
vector <int> x;
for (int i = 0; i < s; ++i){
int mymindisburiedinpornlewl;
cin >> mymindisburiedinpornlewl;
update(mymindisburiedinpornlewl + 1);
x.pb(mymindisburiedinpornlewl + 1);
}
ll answer = inf;
for (int i = 0; i < t; ++i){
int mymindisburiedinpornlewl;
cin >> mymindisburiedinpornlewl;
answer = min(answer, get(mymindisburiedinpornlewl + 1));
}
for (int i: x){
reupdate(i);
}
cout << answer << "\n";
}
}
int main(){
if (fopen(taskname".inp", "r")){
freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
}
faster;
ll tt = 1;
//cin >> tt;
while (tt--){
Init();
}
}