#define taskname "Factories"
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define ff first
#define ss second
using namespace std;
const int maxn = 5e5 + 10;
vector<ii> adj[maxn];
vector<int> dis[maxn];
int sz[maxn], pa[maxn], dp[maxn], ban[maxn], n, q;
void DFSz(int u, int p = -1)
{
sz[u] = 1;
for (auto [v, c]: adj[u]) if (v != p && !ban[v]) DFSz(v, u), sz[u] += sz[v];
}
int getcen(int u, int need, int p = -1)
{
if (sz[u] <= need) return p;
ii big = {0, 0};
for (auto [v, c]: adj[u]) if (v != p && !ban[v]) big = max(big, {sz[v], v});
return getcen(big.ss, need, u);
}
void DFS(int u, int des, int p, int dep)
{
dis[u].emplace_back(dep);
for (auto [v, c]: adj[u]) if (v != p && !ban[v]) DFS(v, des, u, dep+c);
}
void build(int u = 1, int p = 0)
{
DFSz(u);
u = getcen(u, sz[u]/2);
pa[u] = p;
// cerr<<"TREE: "<<p-1<<" "<<u-1<<"\n";
ban[u] = 1;
dp[u] = 1e18;
dis[u].emplace_back(0);
for (auto [v, c]: adj[u]) if (!ban[v])
{
DFS(v, u, u, c);
build(v, u);
}
}
inline void upd(int pos)
{
int u = pos;
for (int i=(int)dis[u].size()-1; i>=0; i--)
{
int j = dis[u][i];
// cerr<<i<<" "<<j<<"\n";
dp[pos] = min(dp[pos], j);
pos = pa[pos];
}
}
inline int qry(int pos)
{
int u = pos;
int ans = 1e18;
for (int i=(int)dis[u].size()-1; i>=0; i--)
{
int j = dis[u][i];
ans = min(ans, dp[pos] + j);
pos = pa[pos];
}
return ans;
}
inline void rollback(int pos) {
int u = pos;
for (int i=(int)dis[u].size()-1; i>=0; i--)
{
int j = dis[u][i];
// cerr<<i<<" "<<j<<"\n";
dp[pos] = 1e18;
pos = pa[pos];
}
}
void Init(int32_t N, int32_t a[], int32_t b[], int32_t d[])
{
for (int i=0; i<=N-2; i++)
{
int u = a[i]+1, v = b[i]+1, c = d[i];
// cerr<<u<<" "<<v<<" "<<c<<"\n";
adj[u].emplace_back(v, c);
adj[v].emplace_back(u, c);
}
build();
// for (int i=1; i<=N; i++) cerr<<"WEIRD: "<<i<<" "<<dis[i].size()<<"\n";
}
int Query(int32_t s, int32_t x[], int32_t t, int32_t y[])
{
// if (s > t)
// {
// swap(s, t);
// swap(x, y);
// }
for (int i=0; i<s; i++) upd(x[i]+1);
int ans = 1e18;
for (int i=0; i<t; i++) ans = min(ans, qry(y[i]+1));
for (int i=0; i<s; i++) rollback(x[i]+1);
return ans;
}
//signed main()
//{
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr); cout.tie(nullptr);
// int32_t a[] = {0, 1, 2, 2, 4, 1}, b[] = {1, 2, 3, 4, 5, 6}, d[] = {4, 4, 5, 6, 5, 3};
// Init(7, a, b, d);
// {
// int32_t q1[] = {0, 6}, q2[] = {3, 4};
// cout<<Query(2, q1, 2, q2)<<"\n"; //returns 12.
// }
// {
// int32_t q1[] = {0, 1, 3}, q2[] = {4, 6};
// cout<<Query(3, q1, 2, q2)<<"\n"; //returns 3.
// }
// {
// int32_t q1[] = {2}, q2[] = {5};
// cout<<Query(1, q1, 1, q2)<<"\n"; //returns 11.
// }
//}
Compilation message
factories.cpp: In function 'void rollback(long long int)':
factories.cpp:79:13: warning: unused variable 'j' [-Wunused-variable]
79 | int j = dis[u][i];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24256 KB |
Output is correct |
2 |
Correct |
253 ms |
42164 KB |
Output is correct |
3 |
Correct |
284 ms |
42512 KB |
Output is correct |
4 |
Correct |
275 ms |
42440 KB |
Output is correct |
5 |
Correct |
284 ms |
42708 KB |
Output is correct |
6 |
Correct |
201 ms |
41832 KB |
Output is correct |
7 |
Correct |
266 ms |
42416 KB |
Output is correct |
8 |
Correct |
300 ms |
42576 KB |
Output is correct |
9 |
Correct |
296 ms |
42672 KB |
Output is correct |
10 |
Correct |
207 ms |
41792 KB |
Output is correct |
11 |
Correct |
276 ms |
42428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
24020 KB |
Output is correct |
2 |
Correct |
2127 ms |
162980 KB |
Output is correct |
3 |
Correct |
3406 ms |
199380 KB |
Output is correct |
4 |
Correct |
728 ms |
109596 KB |
Output is correct |
5 |
Correct |
4005 ms |
250640 KB |
Output is correct |
6 |
Correct |
3279 ms |
200944 KB |
Output is correct |
7 |
Correct |
962 ms |
71392 KB |
Output is correct |
8 |
Correct |
341 ms |
60196 KB |
Output is correct |
9 |
Correct |
1014 ms |
80452 KB |
Output is correct |
10 |
Correct |
937 ms |
72784 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
19 ms |
24256 KB |
Output is correct |
2 |
Correct |
253 ms |
42164 KB |
Output is correct |
3 |
Correct |
284 ms |
42512 KB |
Output is correct |
4 |
Correct |
275 ms |
42440 KB |
Output is correct |
5 |
Correct |
284 ms |
42708 KB |
Output is correct |
6 |
Correct |
201 ms |
41832 KB |
Output is correct |
7 |
Correct |
266 ms |
42416 KB |
Output is correct |
8 |
Correct |
300 ms |
42576 KB |
Output is correct |
9 |
Correct |
296 ms |
42672 KB |
Output is correct |
10 |
Correct |
207 ms |
41792 KB |
Output is correct |
11 |
Correct |
276 ms |
42428 KB |
Output is correct |
12 |
Correct |
15 ms |
24020 KB |
Output is correct |
13 |
Correct |
2127 ms |
162980 KB |
Output is correct |
14 |
Correct |
3406 ms |
199380 KB |
Output is correct |
15 |
Correct |
728 ms |
109596 KB |
Output is correct |
16 |
Correct |
4005 ms |
250640 KB |
Output is correct |
17 |
Correct |
3279 ms |
200944 KB |
Output is correct |
18 |
Correct |
962 ms |
71392 KB |
Output is correct |
19 |
Correct |
341 ms |
60196 KB |
Output is correct |
20 |
Correct |
1014 ms |
80452 KB |
Output is correct |
21 |
Correct |
937 ms |
72784 KB |
Output is correct |
22 |
Correct |
2507 ms |
169216 KB |
Output is correct |
23 |
Correct |
2563 ms |
172956 KB |
Output is correct |
24 |
Correct |
3848 ms |
207020 KB |
Output is correct |
25 |
Correct |
3892 ms |
211084 KB |
Output is correct |
26 |
Correct |
3815 ms |
207964 KB |
Output is correct |
27 |
Correct |
4570 ms |
254520 KB |
Output is correct |
28 |
Correct |
983 ms |
119928 KB |
Output is correct |
29 |
Correct |
3899 ms |
207320 KB |
Output is correct |
30 |
Correct |
3831 ms |
206932 KB |
Output is correct |
31 |
Correct |
3795 ms |
207460 KB |
Output is correct |
32 |
Correct |
1060 ms |
80728 KB |
Output is correct |
33 |
Correct |
340 ms |
60620 KB |
Output is correct |
34 |
Correct |
665 ms |
66528 KB |
Output is correct |
35 |
Correct |
750 ms |
67104 KB |
Output is correct |
36 |
Correct |
920 ms |
69716 KB |
Output is correct |
37 |
Correct |
947 ms |
69900 KB |
Output is correct |