| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1051161 | pera | Factories (JOI14_factories) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define pii pair<int , int>
#define pli pair<int , long long>
#include "factories.h"
using namespace std;
const int MAX = 5e5 + 1;
const long long oo = 1e16;
int T = 0 , n , cen , dead[MAX] , sz[MAX];
long long e[MAX];
vector<int> g[MAX] , order = {0};
vector<long long> w[MAX];
vector<pli> ups[MAX];
void dfs(int u , int p = -1){
sz[u] = 1;
for(int x = 0;x < (int)g[u].size();x ++){
if(g[u][x] != p && !dead[g[u][x]]){
dfs(g[u][x] , u);
sz[u] += sz[g[u][x]];
}
}
}
int centroid(int u , int e , int p = -1){
for(int x = 0;x < (int)g[u].size();x ++){
if(g[u][x] != p && !dead[g[u][x]] && sz[g[u][x]] > e / 2){
return centroid(g[u][x] , e , u);
}
}
return u;
}
void build(int u , int p , long long D){
ups[u].push_back({cen , D});
for(int x = 0;x < (int)g[u].size();x ++){
if(g[u][x] != p && !dead[g[u][x]]){
build(g[u][x] , u , D + w[u][x]);
}
}
}
void solve(int u){
dfs(u);
cen = centroid(u , sz[u]);
for(int x = 0;x < (int)g[cen].size();x ++){
if(!dead[g[cen][x]]){
build(g[cen][x] , cen , w[cen][x]);
}
}
dead[cen] = 1;
for(int x = 0;x < (int)g[cen].size();x ++){
if(!dead[g[cen][x]]){
solve(g[cen][x]);
}
}
}
void Init(int N , int A[] , int B[] , int D[]){
n = N;
for(int i = 0;i < N - 1;i ++){
++A[i] , ++B[i];
g[A[i]].push_back(B[i]);
w[A[i]].push_back(D[i]);
g[B[i]].push_back(A[i]);
w[B[i]].push_back(D[i]);
}
for(int i = 1;i <= N;i ++){
dead[i] = 0;
e[i] = oo;
}
solve(1);
/*for(int u = 1;u <= n;u ++){
for(auto [v , D] : ups[u]){
cout << v << " " << D << endl;
}
}*/
}
long long Query(int S , int X[] , int T , int Y[]){
long long ans = oo;
for(int i = 0;i < T;i ++){
++Y[i];
e[Y[i]] = min(e[Y[i]] , 0);
for(auto [u , D] : ups[Y[i]]){
e[u] = min(e[u] , D);
}
}
for(int i = 0;i < S;i ++){
++X[i];
ans = min(ans , e[X[i]]);
for(auto [u , D] : ups[X[i]]){
ans = min(ans , e[u] + D);
}
}
for(int i = 0;i < T;i ++){
for(auto [u , D] : ups[Y[i]]){
e[u] = oo;
}
}
return ans;
}