#include <bits/stdc++.h>
#include "factories.h"
#define Ni 500050
#define logn 20
#define inf 200000000000000000
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int n, q, nivel[Ni], block[Ni], sz[Ni], tot, pai[Ni], root, tmp = 1, ini[Ni], deep[2*Ni];
ll dist[Ni], ans[Ni];
vector<pii> grafo[Ni];
vector<int> tree[Ni], euler;
pii best, dp[2*Ni][logn];
int last_upd[Ni], cnt_upd = 1;
inline void build()
{
for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(deep[i], euler[i]);
for(int j = 1; j < logn; j++)
{
for(int i = 0; i < euler.size(); i++)
{
if(i + (1<<(j - 1) < 2*Ni)) dp[i][j] = min(dp[i][j - 1], dp[ i + (1<<(j - 1)) ][j - 1]);
else dp[i][j] = dp[i][j - 1];
}
}
}
inline int query(int l, int r)
{
if(l == r) return euler[l];
int e = 31-__builtin_clz(r-l);
return min(dp[l][e], dp[r - (1<<e) + 1][e]).s;
}
inline void dfs(int x, int p)
{
if(ini[x] == 0) ini[x] = tmp;
euler.push_back(x);
tmp ++;
for(int i = 0; i < grafo[x].size(); i++)
{
int v = grafo[x][i].f;
ll peso = (ll)grafo[x][i].s;
if(v == p) continue;
nivel[v] = nivel[x] + 1;
dist[v] = dist[x] + peso;
dfs(v, x);
euler.push_back(x);
tmp ++;
}
}
inline void init()
{
dfs(1, 1);
for(int i = 0; i < euler.size(); i++) deep[i] = nivel[euler[i]];
build();
}
inline int lca(int a, int b)
{
return query(min(ini[a] - 1, ini[b] - 1), max(ini[a] - 1, ini[b] - 1));
}
inline int tam(int x, int p)
{
sz[x] = 1;
for(int i = 0; i < grafo[x].size(); i++)
{
int v = grafo[x][i].f;
if(v == p || block[v]) continue;
sz[x] += tam(v, x);
}
return sz[x];
}
inline void split(int x, int p)
{
int maior = tot - sz[x];
for(int i = 0; i < grafo[x].size(); i++)
{
int v = grafo[x][i].f;
if(v == p || block[v]) continue;
split(v, x);
maior = max(maior, sz[v]);
}
if(maior < best.f) best = pii(maior, x);
}
inline int find_centroid(int x)
{
tot = tam(x, x);
best = pii(2*Ni, 0);
split(x, x);
return best.s;
}
inline int decomp(int x)
{
x = find_centroid(x);
block[x] = 1;
for(auto v: grafo[x])
{
if(block[v.f]) continue;
v.f = decomp(v.f);
tree[x].push_back(v.f);
tree[v.f].push_back(x);
}
return x;
}
inline void dfs2(int x, int p)
{
pai[x] = p;
for(auto v: tree[x])
{
if(v == p) continue;
pai[v] = x;
dfs2(v, x);
}
}
inline ll distancia(int a, int b)
{
return dist[a] + dist[b] - 2*dist[lca(a, b)];
}
inline void paint(int x)
{
ans[x] = 0;
last_upd[x] = cnt_upd;
int u = x;
while(1)
{
if(last_upd[pai[x]] != cnt_upd) ans[pai[x]] = distancia(u, pai[x]);
else ans[pai[x]] = min(ans[pai[x]], distancia(u, pai[x]));
last_upd[pai[x]] = cnt_upd;
if(x == pai[x]) return;
x = pai[x];
}
}
inline void clear(int x)
{
ans[x] = inf;
int u = x;
while(1)
{
ans[pai[x]] = inf;
if(x == pai[x]) return;
x = pai[x];
}
}
ll query(int x)
{
int u = x;
ll resp = inf;
if(last_upd[x] == cnt_upd) resp = min(resp, ans[x]);
while(1)
{
if(last_upd[x] == cnt_upd) resp = min(resp, distancia(x, u) + ans[x]);
if(x == pai[x]) return resp;
x = pai[x];
}
}
void Init(int N_, int A[], int B[], int D[])
{
n = N_;
for(int i = 0; i < Ni; i++) ans[i] = inf;
for(int i = 0; i < n - 1; i++)
{
int a = A[i], b = B[i], c = D[i];
a++, b++;
grafo[a].push_back(pii(b, c));
grafo[b].push_back(pii(a, c));
}
init();
root = decomp(1);
dfs2(root, root);
}
ll Query(int S, int X[], int T, int Y[])
{
ll ans = inf;
++cnt_upd;
for(int i = 0; i < S ; i++) paint(X[i] + 1);
for(int i = 0; i < T; i++) ans = min(ans, query(Y[i] + 1));
//for(int i = 0; i < S; i++) clear(X[i] + 1);
return ans;
}
Compilation message
factories.cpp: In function 'void build()':
factories.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(deep[i], euler[i]);
^
factories.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < euler.size(); i++)
^
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++)
^
factories.cpp: In function 'void init()':
factories.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < euler.size(); i++) deep[i] = nivel[euler[i]];
^
factories.cpp: In function 'int tam(int, int)':
factories.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++)
^
factories.cpp: In function 'void split(int, int)':
factories.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < grafo[x].size(); i++)
^
factories.cpp: In function 'void clear(int)':
factories.cpp:200:6: warning: unused variable 'u' [-Wunused-variable]
int u = x;
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
227440 KB |
Output is correct |
| 2 |
Correct |
589 ms |
227836 KB |
Output is correct |
| 3 |
Correct |
829 ms |
227836 KB |
Output is correct |
| 4 |
Correct |
636 ms |
227836 KB |
Output is correct |
| 5 |
Correct |
749 ms |
227904 KB |
Output is correct |
| 6 |
Correct |
406 ms |
227872 KB |
Output is correct |
| 7 |
Correct |
773 ms |
227836 KB |
Output is correct |
| 8 |
Correct |
836 ms |
227836 KB |
Output is correct |
| 9 |
Correct |
779 ms |
227908 KB |
Output is correct |
| 10 |
Correct |
353 ms |
227872 KB |
Output is correct |
| 11 |
Correct |
733 ms |
227836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
227440 KB |
Output is correct |
| 2 |
Correct |
4119 ms |
266532 KB |
Output is correct |
| 3 |
Correct |
5559 ms |
267912 KB |
Output is correct |
| 4 |
Correct |
1913 ms |
268940 KB |
Output is correct |
| 5 |
Runtime error |
0 ms |
0 KB |
-1: Interrupted system call
|
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5883 ms |
266532 KB |
Output is correct |
| 2 |
Correct |
5466 ms |
266524 KB |
Output is correct |
| 3 |
Runtime error |
0 ms |
0 KB |
-1: Interrupted system call
|
| 4 |
Halted |
0 ms |
0 KB |
- |
