#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
using ll = long long;
using pl = pair<ll,ll>;
using vl = vector<ll>;
#define mp make_pair
#define f first
#define s second
// vectors
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define ins insert
#define pf push_front
#define pb push_back
// loops
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353;
const ll INF = 1e18; // not too close to LLONG_MAX
// #define int ll
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; // for every grid problem!!
const int MAXN = 1e6+5;
const int LOGN = 25;
ll n,current_tree = 0;
vector<pl> g[MAXN];
ll best[MAXN],deleted[MAXN];
ll depth[MAXN];
ll par[MAXN],sub[MAXN];
ll dist[LOGN][MAXN];
// initally all nodes are red
ll LCA(ll u,ll v){
// finds LCA in of u and v in the centroid tree
while(u != v){
if(depth[u] < depth[v])
v = par[v]; // get v a level up
else
u = par[u]; // get u a level up
}
return u;
}
ll compute_dist(ll x,ll y){
ll lc = depth[LCA(x,y)];
return dist[lc][x] + dist[lc][y];
}
void find_subtree(ll u,ll p){
sub[u] = 1;
current_tree++;
trav(P,g[u]){
int v = P.f;
if(deleted[v] == 0 && v != p){
find_subtree(v,u);
sub[u] += sub[v];
}
}
}
ll find_centroid(ll u,ll p){
trav(P,g[u]){
ll v = P.f;
if(deleted[v] == 0 && v !=p && sub[v] > (current_tree / 2)) return find_centroid(v,u);
}
return u;
}
void dfs(ll u,ll p,ll lvl,ll dd){
dist[lvl][u] = dd;
trav(P,g[u]){
ll v = P.f;
ll w = P.s;
if(deleted[v] == 0 && v != p){
dfs(v,u,lvl,dd + w);
}
}
}
void decompose(ll root,ll p){
current_tree = 0;
find_subtree(root,p);
ll cen = find_centroid(root,p);
par[cen] = p;
if(p != -1) depth[cen] = depth[p] + 1;
dfs(cen,p,depth[cen],0);
deleted[cen] = 1;
trav(P,g[cen]){
int v = P.f;
if(deleted[v] == 1) continue;
decompose(v,cen);
}
}
ll query(ll u){
// find the nearest blue node to u
ll ans = best[u];
ll x = u;
u = par[u];
while(u != -1){
ans = min(ans,compute_dist(x,u) + best[u]);
u = par[u];
}
return ans;
}
void update(ll u){
// colour node u to blue
ll x = u;
while(u != -1){
best[u] = min(best[u],compute_dist(u,x));
u = par[u];
}
}
void remove_col(ll u){
// u has to be a blue node
// remove its colour
while(u != -1){
best[u] = INF;
u = par[u];
}
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
FOR(i,0,n-1){A[i]++,B[i]++;
g[A[i]].pb(mp(B[i],D[i]));
g[B[i]].pb(mp(A[i],D[i]));
}
for(int i =1;i<=n;i++) best[i] = INF;
decompose(1,-1);
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i =0;i<S;i++) X[i]++;
for(int i =0;i<T;i++) Y[i]++;
for(int i = 0;i < T;i++){
update(Y[i]);
}
ll ans = INF;
for(int i = 0;i< S;i++){
ans = min(ans,query(X[i]));
}
for(int i =0;i<T;i++){
remove_col(Y[i]);
}
return ans;
}
/* void solve(){
cin >> n;
int q;
cin >> q;
FOR(i,2,n+1){
int u,v,w;
cin >> u >> v >> w;
u++,v++;
g[u].pb(mp(v,w));
g[v].pb(mp(u,w));
}
for(int i =1;i<=n;i++) best[i] = INF;
decompose(1,-1);
FOR(i,1,n+1){
cout << i << " " << par[i] << endl;
}
while(q--){
int s,t;
cin >> s >> t;
vl u(s),v(t);
for(int i =0;i<s;i++) cin >> u[i],u[i]++;
for(int i =0;i<t;i++) cin >> v[i],v[i]++;
for(int i = 0;i < t;i++){
update(v[i]);
}
int ans = INF;
for(int i = 0;i< s;i++){
ans = min(ans,query(u[i]));
}
cout << ans << endl;
for(int i =0;i<t;i++){
remove_col(v[i]);
}
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
// you should actually read the stuff at the bottom
int t=1;
// cin >> t;
while(t--){
solve();
}
} */
/* stuff you should look for
* read the probem 3 more times in case of WA :)
* int overflow, array bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
24300 KB |
Output is correct |
2 |
Correct |
433 ms |
33004 KB |
Output is correct |
3 |
Correct |
521 ms |
42604 KB |
Output is correct |
4 |
Correct |
525 ms |
42476 KB |
Output is correct |
5 |
Correct |
623 ms |
42988 KB |
Output is correct |
6 |
Correct |
310 ms |
42092 KB |
Output is correct |
7 |
Correct |
526 ms |
42604 KB |
Output is correct |
8 |
Correct |
542 ms |
42476 KB |
Output is correct |
9 |
Correct |
628 ms |
42732 KB |
Output is correct |
10 |
Correct |
306 ms |
42092 KB |
Output is correct |
11 |
Correct |
535 ms |
42476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
24044 KB |
Output is correct |
2 |
Correct |
3053 ms |
141156 KB |
Output is correct |
3 |
Correct |
4817 ms |
177380 KB |
Output is correct |
4 |
Correct |
880 ms |
105928 KB |
Output is correct |
5 |
Correct |
6434 ms |
202836 KB |
Output is correct |
6 |
Correct |
5011 ms |
179420 KB |
Output is correct |
7 |
Correct |
2608 ms |
71276 KB |
Output is correct |
8 |
Correct |
479 ms |
59484 KB |
Output is correct |
9 |
Correct |
3147 ms |
75500 KB |
Output is correct |
10 |
Correct |
2592 ms |
72812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
24300 KB |
Output is correct |
2 |
Correct |
433 ms |
33004 KB |
Output is correct |
3 |
Correct |
521 ms |
42604 KB |
Output is correct |
4 |
Correct |
525 ms |
42476 KB |
Output is correct |
5 |
Correct |
623 ms |
42988 KB |
Output is correct |
6 |
Correct |
310 ms |
42092 KB |
Output is correct |
7 |
Correct |
526 ms |
42604 KB |
Output is correct |
8 |
Correct |
542 ms |
42476 KB |
Output is correct |
9 |
Correct |
628 ms |
42732 KB |
Output is correct |
10 |
Correct |
306 ms |
42092 KB |
Output is correct |
11 |
Correct |
535 ms |
42476 KB |
Output is correct |
12 |
Correct |
18 ms |
24044 KB |
Output is correct |
13 |
Correct |
3053 ms |
141156 KB |
Output is correct |
14 |
Correct |
4817 ms |
177380 KB |
Output is correct |
15 |
Correct |
880 ms |
105928 KB |
Output is correct |
16 |
Correct |
6434 ms |
202836 KB |
Output is correct |
17 |
Correct |
5011 ms |
179420 KB |
Output is correct |
18 |
Correct |
2608 ms |
71276 KB |
Output is correct |
19 |
Correct |
479 ms |
59484 KB |
Output is correct |
20 |
Correct |
3147 ms |
75500 KB |
Output is correct |
21 |
Correct |
2592 ms |
72812 KB |
Output is correct |
22 |
Correct |
4223 ms |
165868 KB |
Output is correct |
23 |
Correct |
4200 ms |
170636 KB |
Output is correct |
24 |
Correct |
6902 ms |
185708 KB |
Output is correct |
25 |
Correct |
6867 ms |
189408 KB |
Output is correct |
26 |
Correct |
6931 ms |
185832 KB |
Output is correct |
27 |
Execution timed out |
8106 ms |
204948 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |