Submission #554108

#	Time	Username	Problem	Language	Result	Execution time	Memory
554108		QwertyPi	Factories (JOI14_factories)	C++14	0 / 100	8028 ms	24276 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 5e5 + 13, L = 20;
const ll inf = 1LL << 60;
ll d[N];
int 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{
	ll bit[N];
	void upd(int p, ll 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
		ll 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; ll dis; int colour;
	state(){};
	state(int v, ll d, int c) : v(v), dis(d), colour(c){};
	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);
}
 
struct cmp{
	bool operator() (const int u, const int v){
		return dep[u] < dep[v];
	}
};

ll 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 = 0; j < S; j++) c0.upd(op[X[j]], 1);
	for(int j = 0; j < T; j++) c1.upd(op[Y[j]], 1);
	ll ans = inf;
	priority_queue<int, vector<int>, cmp> pq;
	for(int j = 0; j < S; j++){
		pq.push(dep[X[j]]);
		in_pq[dep[X[j]]] = true;
		qry[dep[X[j]]].resize(0);
	}
	for(int j = 0; j < T; j++){
		pq.push(dep[Y[j]]);
		in_pq[dep[Y[j]]] = true;
		qry[dep[Y[j]]].resize(0);
	}
	for(int j = 0; j < S; j++){
		int v = X[j];
		qry[dep[v]].pb(v, 0, 0);
	}
	for(int j = 0; j < T; j++){
		int v = Y[j];
		qry[dep[v]].pb(v, 0, 1);
	}
	int j = -1;
	for(j; pq.size();){
		j = pq.top(); pq.pop(); in_pq[j] = false;
		if(j > 0){
			if(dp[j][1] != inf){
				int _lca = 0;
				int l = c0.qry_pos(c0.qry(op[j] - 1)), r = c0.qry_pos(c0.qry(op[j] + sz[j] - 1) + 1);
				if(l < 0 && r > n - 1) _lca = 0;
				else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(j, euler[r]) : lca(euler[l], j);
				else{
					int llca = lca(euler[l], j), rlca = lca(j, euler[r]);
					_lca = (dep[llca] > dep[rlca] ? llca : rlca);
				}
				if(_lca == j) _lca = p[j];
				if(!in_pq[dep[_lca]]) in_pq[dep[_lca]] = true, dp[_lca][0] = dp[_lca][1] = inf, pq.push(dep[_lca]);
				ll new_dis = dp[j][1] + d[j] - d[_lca];
				ans = min(ans, dp[_lca][0] + new_dis);
				dp[_lca][1] = min(dp[_lca][1], new_dis);
			}
			if(dp[j][0] != inf){
				int _lca = 0;
				int l = c1.qry_pos(c1.qry(op[j] - 1)), r = c1.qry_pos(c1.qry(op[j] + sz[j] - 1) + 1);
				if(l < 0 && r > n - 1) _lca = 0;
				else if(l < 0 || r > n - 1) _lca = l < 0 ? lca(j, euler[r]) : lca(euler[l], j);
				else{
					int llca = lca(euler[l], j), rlca = lca(j, euler[r]);
					_lca = (dep[llca] > dep[rlca] ? llca : rlca);
				}
				if(_lca == j) _lca = p[j];
				if(!in_pq[dep[_lca]]) in_pq[dep[_lca]] = true, dp[_lca][0] = dp[_lca][1] = inf, pq.push(dep[_lca]);
				ll new_dis = dp[j][0] + d[j] - d[_lca];
				ans = min(ans, dp[_lca][1] + new_dis);
				dp[_lca][1] = min(dp[_lca][1], new_dis);
			}
		}
	}
	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;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:23:15: warning: variable 'son' set but not used [-Wunused-but-set-variable]
   23 |  int out = 0, son = -1;
      |               ^~~
factories.cpp: In function 'void bl(int)':
factories.cpp:70:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |    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];
      |                                                    ~~^~~
factories.cpp:70:100: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   70 |    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];
      |                                                                                                  ~~^~~
factories.cpp: In function 'long long int Query(int32_t, int32_t*, int32_t, int32_t*)':
factories.cpp:136:6: warning: statement has no effect [-Wunused-value]
  136 |  for(j; pq.size();){
      |      ^

• Subtask 1: 0 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67