#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
typedef long long ll;
constexpr int LIM = 1e5;
vector<pair<int, int> >g[LIM + 10];
unordered_map<int, ll>dist[LIM + 10];
unordered_map<int, ll>cnt;
int siz[LIM + 10];
int oj[LIM + 10];
bool vis[LIM + 10];
void cntsiz(int v, int o) {
siz[v] = 1;
for(auto x : g[v]) {
if(x.st != o) {
cntsiz(x.st, v);
siz[v] += siz[x.st];
}
}
}
void cntdist(int v, int o, int kt) {
for(auto x : g[v]) {
if(x.st != o && !vis[x.st]) {
dist[kt][x.st] = dist[kt][v] + x.nd;
cntdist(x.st, v, kt);
}
}
}
int find(int a) {
for(auto x : g[a]) {
if(!vis[x.st] && siz[x.st] > siz[a] / 2) {
int tmp = siz[x.st];
siz[x.st] = siz[a];
siz[a] -= tmp;
return find(x.st);
}
}
return a;
}
void dfs(int v, int o) {
int c = find(v);
oj[c] = o;
vis[c] = 1;
cntdist(c, c, c);
for(auto x : g[c]) {
if(!vis[x.st]) {
dfs(x.st, c);
}
}
}
void Init(int n, int a[], int b[], int c[]) {
for(int i = 0; i < n - 1; i++) {
g[a[i]].push_back({b[i], c[i]});
g[b[i]].push_back({a[i], c[i]});
}
cntsiz(1, 1);
dfs(1, 0);
}
ll Query(int n, int a[], int m, int b[]) {
for(int i = 0; i < n; i++) {
int tmp = a[i];
while(tmp > 0) {
if(cnt.count(tmp)) {
cnt[tmp] = min(cnt[tmp], dist[tmp][a[i]]);
}
else {
cnt[tmp] = dist[tmp][a[i]];
}
tmp = oj[tmp];
}
}
ll ans = 1e18;
for(int i = 0; i < m; i++) {
int tmp = b[i];
while(tmp > 0) {
if(cnt.count(tmp)) {
ans = min(ans, cnt[tmp] + dist[tmp][b[i]]);
}
tmp = oj[tmp];
}
}
cnt.clear();
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
8788 KB |
Output is correct |
| 2 |
Incorrect |
830 ms |
27768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
8404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
8788 KB |
Output is correct |
| 2 |
Incorrect |
830 ms |
27768 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
