#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
int _N;
vector<vector<ii> > edges;
int parent[500000][20];
int depth[500000];
ll rootdist[500000];
int twopow[20];
int pff[524289];
int lcadp[5000][5000];
void dfs(int x, int d, ll dst) {
depth[x] = d;
rootdist[x] = dst;
for (int i = 0; i < edges[x].size(); i++) {
if (edges[x][i].first == parent[x][0]) continue;
parent[edges[x][i].first][0] = x;
dfs(edges[x][i].first, d+1, dst + edges[x][i].second);
}
}
void prt(int x, int e) {
if (depth[x] >= twopow[e]) {
int q = parent[x][e-1];
parent[x][e] = parent[q][e-1];
}
for (int i = 0; i < edges[x].size(); i++) {
if (edges[x][i].first == parent[x][0]) continue;
prt(edges[x][i].first, e);
}
}
int lca(int a, int b) {
if (lcadp[a][b] != -1) return lcadp[a][b];
int _a = a, _b = b;
if (depth[a] > depth[b]) {
int t = a;
a = b;
b = t;
}
int dif = depth[b] - depth[a];
int c = 0;
while (dif) {
if (dif & 1) {
b = parent[b][c];
}
c++;
dif >>= 1;
}
/*while (depth[b] > depth[a]) {
int dif = depth[b] - depth[a];
//cerr << b << endl;
dif = dif & -dif;
int c = pff[dif];
b = parent[b][c];
}*/
int d = depth[a];
for (int x = 19; x >= 0; x--) {
int q = twopow[x];
if (q > d) continue;
if (parent[a][x] != parent[b][x]) {
a = parent[a][x];
b = parent[b][x];
}
}
int ans = a;
if (a != b) ans = parent[a][0];
//cerr << a << " " << b << " " << ans << endl;
lcadp[_a][_b] = lcadp[_b][_a] = ans;
return ans;
}
ll dst(int a, int b) {
int c = lca(a, b);
return rootdist[a] + rootdist[b] - 2 * rootdist[c];
}
void Init(int N, int A[], int B[], int D[]) {
memset(lcadp, -1, sizeof(lcadp));
_N = N;
edges.resize(N);
for (int i = 0; i < N; i++) {
edges[A[i]].pb(mp(B[i], D[i]));
edges[B[i]].pb(mp(A[i], D[i]));
}
parent[0][0] = -1;
dfs(0, 0, 0);
twopow[0] = 1;
//pff[1] = 0;
for (int i = 1; i < 20; i++) {
twopow[i] = (int) pow(2, i);
//pff[twopow[i]] = i;
prt(0, i);
}
}
long long Query(int S, int X[], int T, int Y[]) {
ll best = (ll)1e18;
for (int i = 0; i < S; i++) {
for (int j = 0; j < T; j++) {
best = min(best, dst(X[i], Y[j]));
}
}
return best;
}
Compilation message
factories.cpp: In function 'void dfs(int, int, ll)':
factories.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
factories.cpp: In function 'void prt(int, int)':
factories.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges[x].size(); i++) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
169104 KB |
Output is correct |
| 2 |
Execution timed out |
6000 ms |
169428 KB |
Execution timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
169104 KB |
Output is correct |
| 2 |
Runtime error |
3016 ms |
199568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3106 ms |
199568 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
