| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 372585 | erfanmir | 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.
// In the name of god
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#include "factories.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template < class T > using ordered_set = tree < T , null_type , less < T > , rb_tree_tag , tree_order_statistics_node_update >;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(),(x).end()
#define lc(x) (x) << 1
#define rc(x) (x) << 1 | 1
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);
#define mp make_pair
ll poww(ll a, ll b, ll md) {
ll ans = 1;
for(; b; b >>= 1, a = a * a % md){
if(b & 1){
ans = ans * a % md;
}
}
return ans % md;
}
const int MAXN = 5e5 + 10;
const int MAXLG = 20;
const int MOD = 1e9 + 7;
const int MOD2 = 998244353;
const ll INF = 1e18;
int n, par[MAXN][MAXLG], h[MAXN], st[MAXN], ft[MAXN], cnt, r[MAXN], b[MAXN], stk[MAXN];
vector<int> g[MAXN];
vector<pii> adj[MAXN];
ll dp[MAXN], rd[MANX], bd[MAXN];
void dfs(int v = 1){
st[v] = cnt++;
for(auto u : adj[v]){
if(u.F == par[v][0]){
continue;
}
h[u.F] = h[v] + 1;
dp[u.F] = dp[v] + u.S;
par[u.F][0] = v;
dfs(u.F);
}
ft[v] = cnt;
}
int edq(int u, int val){
for(int i = 0; i < MAXLG; i++){
if(val & 1){
u = par[u][i];
}
val /= 2;
}
return u;
}
int lca(int v, int u){
if(h[v] > h[u]){
swap(v, u);
}
u = edq(u, h[u] - h[v]);
if(v == u){
return v;
}
for(int i = MAXLG - 1; ~i; i--){
if(par[v][i] == par[u][i]){
continue;
}
v = par[v][i];
u = par[u][i];
}
return par[v][0];
}
bool cmp(int a, int b){
return st[a] < st[b];
}
void Init(int N, int A[], int B[], int D){
n = N;
for(int i = 0; i < n - 1; i++){
adj[A[i] + 1].push_back(mp(B[i] + 1, D[i]));
adj[B[i] + 1].push_back(mp(A[i] + 1, D[i]));
}
dfs();
for(int i = 1; i <= n; i++){
for(int j = 1; j < MAXLG; j++){
par[i][j] = par[par[i][j - 1]][j - 1];
}
}
}
void sfd(int v){
rd[v] = bd[v] = INF;
if(b[v]){
bd[v] = 0;
}
if(r[v]){
rd[v] = 0;
}
for(auto u : g[v]){
sfd(u);
bd[v] = min(bd[v], bd[u] + dp[v] + dp[u] - 2 * dp[lca(v, u)]);
rd[v] = min(rd[v], rd[u] + dp[v] + dp[u] - 2 * dp[lca(v, u)]);
}
}
ll Query(int S, int X[], int T, int Y[]){
ll ans = INF;
vector<int> vec;
for(int i = 0; i < S; i++){
vec.push_back(X[i] + 1);
b[X[i] + 1] = 1;
}
for(int i = 0; i < T; i++){
vec.push_back(Y[i] + 1);
r[Y[i] + 1] = 1;
}
sort(all(vec), cmp);
for(int i = 0; i < S + T - 1; i++){
vec.push_back(lca(vec[i], vec[i + 1]));
}
vec.push_back(lca(vec[0], vec[S + T - 1]));
sort(all(vec));
erase(unique(all(vec)), vec.end());
int ptr = 0;
stk[++ptr] = vec[0];
for(int i = 1; i < (int)vec.size(); i++){
while(st[stk[ptr]] > st[vec[i]] || ft[vec[i]] > ft[stk[ptr]]){
stk[ptr] = 0;
ptr--;
}
g[stk[ptr]].push_back(vec[i]);
stk[++ptr] = vec[i];
}
sfd(vec[0]);
for(auto v : vec){
g[v].clear();
ans = min(ans, bd[v] + rd[v]);
b[v] = r[v] = 0;
}
return ans;
}