| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 920902 |
2024-02-03T07:31:41 Z |
Gr47 |
Factories (JOI14_factories) |
C++17 |
|
8000 ms |
261360 KB |
#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
class CentroidDecomposition
{
private:
int n;
vector<bool> vis;
vector<int> sz;
const vector<vector<int>> &tree;
int find_size(int v, int p = -1)
{
if (vis[v])
return 0;
sz[v] = 1;
for (const int &x : tree[v])
if (x != p)
sz[v] += find_size(x, v);
return sz[v];
}
int find_centroid(int v, int p, int cur_sz)
{
for (const int &x : tree[v])
if (x != p)
if (!vis[x] && sz[x] > (cur_sz / 2))
return find_centroid(x, v, cur_sz);
return v;
}
void init_centroid(int v, int p)
{
find_size(v);
int c = find_centroid(v, -1, sz[v]);
vis[c] = true;
centroid_par[c] = p;
if (p == -1)
root = c;
else
centorid_tree[p].push_back(c);
for (const int &x : tree[c])
if (!vis[x])
init_centroid(x, c);
}
public:
vector<vector<int>> centorid_tree;
vector<int> centroid_par;
int root;
CentroidDecomposition(vector<vector<int>> &_tree) : tree(_tree)
{
root = 0;
n = tree.size();
centorid_tree.resize(n);
vis.resize(n, false);
sz.resize(n, 0);
centroid_par.resize(n, -1);
init_centroid(0, -1);
}
};
struct LCA
{
int N;
static const int D = 20;
vector<vector<int>> table;
vector<vector<long long>> seg;
vector<int> depth;
LCA(vector<vector<int>> &tree, map<pair<int, int>, long long> &edge)
{
N = tree.size();
depth.assign(N, 0);
table.assign(D, vector<int>(N, -1));
seg.assign(D, vector<long long>(N, 0LL));
dfs(0, -1, tree, edge);
for (int i = 1; i < D; i++)
{
for (int u = 0; u < N; u++)
{
if (table[i - 1][u] >= 0)
{
table[i][u] = table[i - 1][table[i - 1][u]];
seg[i][u] = seg[i - 1][table[i - 1][u]] + seg[i - 1][u];
}
else
table[i][u] = -1;
}
}
}
void dfs(int u, int p, vector<vector<int>> &tree, map<pair<int, int>, long long> &edge)
{
table[0][u] = p;
if (p != -1)
seg[0][u] = edge[make_pair(u, p)];
for (int v : tree[u])
{
if (v == p)
continue;
depth[v] = depth[u] + 1;
dfs(v, u, tree, edge);
}
}
int up(int u, int dist)
{
for (int i = D - 1; i >= 0; i--)
{
if ((dist & (1 << i)) > 0)
{
u = table[i][u];
if (u == -1)
return -1;
}
}
return u;
}
int lca(int u, int v)
{
if (depth[u] < depth[v])
{
return lca(v, u);
}
int diff = depth[u] - depth[v];
u = up(u, diff);
if (u == v)
return u;
for (int i = D - 1; i >= 0; i--)
{
if (table[i][u] != table[i][v])
{
u = table[i][u];
v = table[i][v];
}
}
return table[0][u];
}
int distance(int u, int v)
{
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
// get combined segment for [u(0),u(1),u(2),....u(up_walk)] where u(i+1) is parent of u(i) and u(0) = u
long long combined_segment(int u, int up_walk)
{
long long res = 0;
for (int i = D - 1; i >= 0; i--)
{
if ((up_walk & (1 << i)) > 0)
{
res += seg[i][u];
u = table[i][u];
}
}
return res;
}
long long path_segment(int u, int v)
{
int lc = lca(u, v);
return combined_segment(u, depth[u] - depth[lc]) + combined_segment(v, depth[v] - depth[lc]);
}
};
LCA *lca;
CentroidDecomposition *cd;
vector<long long> best;
const long long inf = 1e18;
void Init(int N, int A[], int B[], int D[])
{
map<pair<int, int>, long long> edge;
vector<vector<int>> tree(N);
for (int i = 0; i < N - 1; i++)
{
tree[A[i]].push_back(B[i]);
tree[B[i]].push_back(A[i]);
edge[make_pair(A[i], B[i])] = D[i];
edge[make_pair(B[i], A[i])] = D[i];
}
lca = new LCA(tree, edge);
cd = new CentroidDecomposition(tree);
best.resize(N, inf);
}
void add_node(int u)
{
best[u] = 0;
int p = u;
while (p != cd->root)
{
p = cd->centroid_par[p];
best[p] = min(best[p], lca->path_segment(u, p));
}
}
void rem_node(int u)
{
best[u] = inf;
int p = u;
while (p != cd->root)
{
p = cd->centroid_par[p];
if (best[p] == inf)
break;
best[p] = inf;
}
}
long long get_min_dist(int u)
{
long long ans = inf;
int cur = u;
while (cur != -1)
{
ans = min(ans, best[cur] + lca->path_segment(u, cur));
cur = cd->centroid_par[cur];
}
return ans;
}
long long Query(int S, int X[], int T, int Y[])
{
long long ans = inf;
for (int i = 0; i < S; i++)
add_node(X[i]);
for (int i = 0; i < T; i++)
ans = min(ans, get_min_dist(Y[i]));
for (int i = 0; i < S; i++)
rem_node(X[i]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
17240 KB |
Output is correct |
| 2 |
Correct |
985 ms |
28244 KB |
Output is correct |
| 3 |
Correct |
2071 ms |
28348 KB |
Output is correct |
| 4 |
Correct |
2120 ms |
28332 KB |
Output is correct |
| 5 |
Correct |
2629 ms |
28684 KB |
Output is correct |
| 6 |
Correct |
321 ms |
28196 KB |
Output is correct |
| 7 |
Correct |
2080 ms |
28496 KB |
Output is correct |
| 8 |
Correct |
2195 ms |
28224 KB |
Output is correct |
| 9 |
Correct |
2549 ms |
28752 KB |
Output is correct |
| 10 |
Correct |
289 ms |
28192 KB |
Output is correct |
| 11 |
Correct |
2045 ms |
28504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
16988 KB |
Output is correct |
| 2 |
Correct |
6917 ms |
255860 KB |
Output is correct |
| 3 |
Execution timed out |
8099 ms |
261360 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
17240 KB |
Output is correct |
| 2 |
Correct |
985 ms |
28244 KB |
Output is correct |
| 3 |
Correct |
2071 ms |
28348 KB |
Output is correct |
| 4 |
Correct |
2120 ms |
28332 KB |
Output is correct |
| 5 |
Correct |
2629 ms |
28684 KB |
Output is correct |
| 6 |
Correct |
321 ms |
28196 KB |
Output is correct |
| 7 |
Correct |
2080 ms |
28496 KB |
Output is correct |
| 8 |
Correct |
2195 ms |
28224 KB |
Output is correct |
| 9 |
Correct |
2549 ms |
28752 KB |
Output is correct |
| 10 |
Correct |
289 ms |
28192 KB |
Output is correct |
| 11 |
Correct |
2045 ms |
28504 KB |
Output is correct |
| 12 |
Correct |
5 ms |
16988 KB |
Output is correct |
| 13 |
Correct |
6917 ms |
255860 KB |
Output is correct |
| 14 |
Execution timed out |
8099 ms |
261360 KB |
Time limit exceeded |
| 15 |
Halted |
0 ms |
0 KB |
- |
