//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#include "factories.h"
#define TASK "TESTCODE"
#define Log2(x) 31 - __builtin_clz(x)
using namespace std;
const int N = 5e5, cbit = 19;
const long long oo = 1e18;
vector<pair<int, int> > Adj[N + 1];
long long dp[N + 1], sum[N + 1];
int f[2 * N + 1][cbit + 1], par[N + 1], sz[N + 1], depth[N + 1], timer, logg[2 * N + 1], pos[N + 1];
bool visited[N + 1];
void DFS(int u, int p)
{
f[++timer][0] = u;
logg[timer] = logg[timer >> 1] + 1;
pos[u] = timer;
dp[u] = oo;
for (auto x : Adj[u])
{
int v = x.first, w = x.second;
if (v == p)
{
continue;
}
f[++timer][0] = u;
logg[timer] = logg[timer >> 1] + 1;
depth[v] = depth[u] + 1;
sum[v] = sum[u] + w;
DFS(v, u);
}
}
int LCA(int u, int v)
{
if (pos[u] > pos[v])
{
swap(u, v);
}
int k = logg[pos[v] - pos[u] + 1];
u = f[pos[u]][k];
v = f[pos[v] - (1 << k) + 1][k];
if (depth[u] < depth[v])
{
return u;
}
return v;
}
long long dis(int u, int v)
{
return sum[u] + sum[v] - 2 * sum[LCA(u, v)];
}
void CenDFS(int u, int p)
{
sz[u] = 1;
for (auto l : Adj[u])
{
int v = l.first, w = l.second;
if (visited[v] || v == p)
{
continue;
}
CenDFS(v, u);
sz[u] += sz[v];
}
}
int Find_Centroid(int u, int p, int x)
{
for (auto l : Adj[u])
{
int v = l.first, w = l.second;
if (visited[v] || v == p)
{
continue;
}
if (sz[v] > x/2)
{
return Find_Centroid(v, u, x);
}
}
return u;
}
int BuildCentroid(int u)
{
CenDFS(u, -1);
int root = Find_Centroid(u, -1, sz[u]);
visited[root] = true;
//cerr << root << '\n';
for (auto l : Adj[root])
{
int v = l.first, w = l.second;
if (visited[v])
{
continue;
}
par[BuildCentroid(v)] = root;
}
return root;
}
void Init(int N, int A[], int B[], int D[])
{
for (int i = 0; i < N - 1; ++ i)
{
Adj[A[i]].push_back({B[i], D[i]});
Adj[B[i]].push_back({A[i], D[i]});
}
logg[0] = -1;
DFS(0, -1);
par[BuildCentroid(0)] = -1;
for (int k = 1; k <= logg[timer]; ++ k)
{
for (int i = 1; i <= timer; ++ i)
{
int j = i + (1 << (k - 1));
if (j > timer)
{
f[i][k] = f[i][k - 1];
}
else
{
int u = f[i][k - 1], v = f[j][k - 1];
if (depth[u] < depth[v])
{
f[i][k] = u;
}
else
{
f[i][k] = v;
}
}
}
}
}
void update(int u, int t)
{
for (int v = u; v != -1; v = par[v])
{
if (t)
{
dp[v] = min(dp[v], dis(u, v));
}
else
{
dp[v] = oo;
}
}
}
long long get(int u)
{
long long ret = oo;
for (int v = u; v != -1; v = par[v])
{
ret = min(ret, dp[v] + dis(u, v));
}
return ret;
}
long long Query(int S, int X[], int T, int Y[])
{
long long res = oo;
for (int i = 0; i < S; ++ i)
{
update(X[i], 1);
}
for (int i = 0; i < T; ++ i)
{
res = min(res, get(Y[i]));
}
for (int i = 0; i < S; ++ i)
{
update(X[i], 0);
}
return res;
}
/*void read()
{
int A[] = {0, 1, 2, 2, 4, 1};
int B[] = {1, 2, 3, 4, 5, 6};
int D[] = {4, 4, 5, 6, 5, 3};
Init(7, A, B, D);
int X[] = {0, 1, 3};
int Y[] = {4, 6};
cout << Query(3, X, 2, Y);
}
void solve()
{
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen(TASK".INP", "r"))
{
freopen(TASK".INP", "r", stdin);
//freopen(TASK".OUT", "w", stdout);
}
int t = 1;
bool typetest = false;
if (typetest)
{
cin >> t;
}
for (int __ = 1; __ <= t; ++ __)
{
//cout << "Case " << __ << ": ";
read();
solve();
}
}*/
Compilation message
factories.cpp: In function 'void CenDFS(int, int)':
factories.cpp:59:26: warning: unused variable 'w' [-Wunused-variable]
59 | int v = l.first, w = l.second;
| ^
factories.cpp: In function 'int Find_Centroid(int, int, int)':
factories.cpp:72:26: warning: unused variable 'w' [-Wunused-variable]
72 | int v = l.first, w = l.second;
| ^
factories.cpp: In function 'int BuildCentroid(int)':
factories.cpp:92:26: warning: unused variable 'w' [-Wunused-variable]
92 | int v = l.first, w = l.second;
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
12628 KB |
Output is correct |
2 |
Correct |
381 ms |
30856 KB |
Output is correct |
3 |
Correct |
472 ms |
30760 KB |
Output is correct |
4 |
Correct |
505 ms |
30896 KB |
Output is correct |
5 |
Correct |
502 ms |
31032 KB |
Output is correct |
6 |
Correct |
241 ms |
30836 KB |
Output is correct |
7 |
Correct |
442 ms |
30800 KB |
Output is correct |
8 |
Correct |
446 ms |
30856 KB |
Output is correct |
9 |
Correct |
545 ms |
31152 KB |
Output is correct |
10 |
Correct |
227 ms |
30876 KB |
Output is correct |
11 |
Correct |
456 ms |
30888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
12356 KB |
Output is correct |
2 |
Correct |
2513 ms |
160496 KB |
Output is correct |
3 |
Correct |
3290 ms |
162132 KB |
Output is correct |
4 |
Correct |
1061 ms |
160856 KB |
Output is correct |
5 |
Correct |
4384 ms |
191424 KB |
Output is correct |
6 |
Correct |
3211 ms |
164184 KB |
Output is correct |
7 |
Correct |
1686 ms |
60420 KB |
Output is correct |
8 |
Correct |
525 ms |
61140 KB |
Output is correct |
9 |
Correct |
1747 ms |
64872 KB |
Output is correct |
10 |
Correct |
1547 ms |
61776 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
12628 KB |
Output is correct |
2 |
Correct |
381 ms |
30856 KB |
Output is correct |
3 |
Correct |
472 ms |
30760 KB |
Output is correct |
4 |
Correct |
505 ms |
30896 KB |
Output is correct |
5 |
Correct |
502 ms |
31032 KB |
Output is correct |
6 |
Correct |
241 ms |
30836 KB |
Output is correct |
7 |
Correct |
442 ms |
30800 KB |
Output is correct |
8 |
Correct |
446 ms |
30856 KB |
Output is correct |
9 |
Correct |
545 ms |
31152 KB |
Output is correct |
10 |
Correct |
227 ms |
30876 KB |
Output is correct |
11 |
Correct |
456 ms |
30888 KB |
Output is correct |
12 |
Correct |
8 ms |
12356 KB |
Output is correct |
13 |
Correct |
2513 ms |
160496 KB |
Output is correct |
14 |
Correct |
3290 ms |
162132 KB |
Output is correct |
15 |
Correct |
1061 ms |
160856 KB |
Output is correct |
16 |
Correct |
4384 ms |
191424 KB |
Output is correct |
17 |
Correct |
3211 ms |
164184 KB |
Output is correct |
18 |
Correct |
1686 ms |
60420 KB |
Output is correct |
19 |
Correct |
525 ms |
61140 KB |
Output is correct |
20 |
Correct |
1747 ms |
64872 KB |
Output is correct |
21 |
Correct |
1547 ms |
61776 KB |
Output is correct |
22 |
Correct |
3055 ms |
167624 KB |
Output is correct |
23 |
Correct |
3080 ms |
170348 KB |
Output is correct |
24 |
Correct |
4830 ms |
170312 KB |
Output is correct |
25 |
Correct |
4689 ms |
174184 KB |
Output is correct |
26 |
Correct |
4518 ms |
170472 KB |
Output is correct |
27 |
Correct |
5920 ms |
194196 KB |
Output is correct |
28 |
Correct |
1256 ms |
171332 KB |
Output is correct |
29 |
Correct |
4901 ms |
170324 KB |
Output is correct |
30 |
Correct |
4550 ms |
169536 KB |
Output is correct |
31 |
Correct |
4560 ms |
170124 KB |
Output is correct |
32 |
Correct |
2323 ms |
65728 KB |
Output is correct |
33 |
Correct |
544 ms |
61600 KB |
Output is correct |
34 |
Correct |
1179 ms |
58188 KB |
Output is correct |
35 |
Correct |
1219 ms |
58152 KB |
Output is correct |
36 |
Correct |
1517 ms |
58964 KB |
Output is correct |
37 |
Correct |
1458 ms |
58796 KB |
Output is correct |