| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 554050 | QwertyPi | Factories (JOI14_factories) | C++14 | 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 "factories.h"
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
const int N = 5e5 + 13, L = 20;
const int inf = 1LL << 60;
int d[N], p[N], dep[N], sz[N];
vector<pii> G[N];
int timer = 0, timer2 = 0, op[N * 2], ed[N * 2], op2[N * 2], ed2[N * 2];
int euler[N], euler2[N * 2];
int st[N][L];
int n;
void dfs(int v, int par = -1){
euler[timer] = v, op[v] = timer++, sz[v] = 1;
euler2[timer2] = v, op2[v] = timer2++;
int out = 0, son = -1;
for(auto i : G[v]){
if(i.fi != par){
d[i.fi] = d[v] + i.se;
p[i.fi] = v;
dep[i.fi] = dep[v] + 1;
dfs(i.fi, v);
euler2[timer2++] = v;
out++; son = i.fi;
sz[v] += sz[i.fi];
}
}
ed[v] = timer;
ed2[v] = timer2 - 1;
}
struct Fenwick{
int bit[N];
void upd(int p, int v){
p++;
for(int i = p; i < N; i += i & -i){
bit[i] += v;
}
}
int qry(int p){
p++;
int ret = 0;
for(int i = p; i; i -= i & -i){
ret += bit[i];
}
return ret;
}
int qry_pos(int v){ // 1-base, >= 1
int ret = 0, val = 0;
for(int j = 19; j >= 0; j--){
if(ret + (1 << j) >= N) continue;
if(val + bit[ret + (1 << j)] < v) val += bit[ret + (1 << j)], ret += (1 << j);
}
return ret;
}
} c0, c1;
void bl(int n){
for(int i = 0; i < n * 2 - 1; i++) st[i][0] = euler2[i];
for(int j = 1; j < 20; j++){
for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){
st[i][j] = dep[st[i][j - 1]] < dep[st[i + (1 << j - 1)][j - 1]] ? st[i][j - 1] : st[i + (1 << j - 1)][j - 1];
}
}
}
int lca(int x, int y){
int a = min(op2[x], op2[y]), b = max(ed2[x], ed2[y]);
int l = __lg(b - a + 1);
int ret = dep[st[a][l]] < dep[st[b - (1 << l) + 1][l]] ? st[a][l] : st[b - (1 << l) + 1][l];
return ret;
}
struct state{
int v, dis, colour;
bool operator< (const state& o) const{
return v < o.v;
}
};
vector<state> qry[N];
void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) {
n = N;
for(int i = 0; i < N - 1; i++){
G[B[i]].pb({A[i], D[i]});
G[A[i]].pb({B[i], D[i]});
}
dfs(0);
bl(N);
}
int dp[N][2];
bool in_pq[N];
long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) {
for(int j = N - 1; j >= 0; j--) qry[j].clear();
for(int j = 0; j < S; j++){
int v = X[j];
qry[dep[v]].pb({v, d[v] - d[v], 0});
}
for(int j = 0; j < T; j++){
int v = Y[j];
qry[dep[v]].pb({v, d[v] - d[v], 1});
}
for(int j = 0; j < S; j++) c0.upd(op[X[j]], 1);
for(int j = 0; j < T; j++) c1.upd(op[Y[j]], 1);
int ans = inf;
priority_queue<int> pq;
for(int j = 0; j < S; j++){
pq.push(dep[X[j]]);
in_pq[dep[X[j]]] = true;
}
for(int j = 0; j < T; j++){
pq.push(dep[Y[j]]);
in_pq[dep[Y[j]]] = true;
}
int j = -1;
while(j = N - 1; j >= 0; j--){
if(!in_pq[j]) continue;
// j = pq.top(); pq.pop(); in_pq[j] = false;
vector<state> nxt;
for(auto k : qry[j]) dp[k.v][0] = dp[k.v][1] = inf;
for(auto k : qry[j]){
ans = min(ans, dp[k.v][1 - k.colour] + k.dis);
if(dp[k.v][k.colour] == inf) nxt.push_back({k.v, 0, k.colour});
dp[k.v][k.colour] = min(dp[k.v][k.colour], k.dis);
}
for(auto& k : nxt){
k.dis = dp[k.v][k.colour];
}
if(j > 0){
for(auto k : nxt){
int _lca = 0;
if(k.colour){
int l = c0.qry_pos(c0.qry(op[k.v] - 1)), r = c0.qry_pos(c0.qry(op[k.v] + sz[k.v] - 1) + 1);
if(l < 0 && r > n - 1) _lca = 0;
else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(k.v, euler[r]) : lca(euler[l], k.v);
else{
int llca = lca(euler[l], k.v), rlca = lca(k.v, euler[r]);
_lca = (dep[llca] > dep[rlca] ? llca : rlca);
}
}else{
int l = c1.qry_pos(c1.qry(op[k.v] - 1)), r = c1.qry_pos(c1.qry(op[k.v] + sz[k.v] - 1) + 1);
if(l < 0 && r > n - 1) _lca = 0;
else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(k.v, euler[r]) : lca(euler[l], k.v);
else{
int llca = lca(euler[l], k.v), rlca = lca(k.v, euler[r]);
_lca = (dep[llca] > dep[rlca] ? llca : rlca);
}
}
if(_lca == k.v) _lca = p[k.v];
qry[dep[_lca]].pb({_lca, k.dis + d[k.v] - d[_lca], k.colour});
if(!in_pq[dep[_lca]]) in_pq[dep[_lca]] = true, pq.push(dep[_lca]);
}
}
}
for(int j = 0; j < S; j++) c0.upd(op[X[j]], -1);
for(int j = 0; j < T; j++) c1.upd(op[Y[j]], -1);
return ans;
}