Submission #554083

#	Time	Username	Problem	Language	Result	Execution time	Memory
554083		QwertyPi	Factories (JOI14_factories)	C++14	15 / 100	2035 ms	412044 KiB

factories

#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 = 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;
		qry[dep[X[j]]].clear();
	}
	for(int j = 0; j < T; j++){
		pq.push(dep[Y[j]]);
		in_pq[dep[Y[j]]] = true;
		qry[dep[Y[j]]].clear();
	}
	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;
	int _p = 1e6;
	for(j; pq.size();){
		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);
		}
		qry[j].clear();
		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];
				if(!in_pq[dep[_lca]]) in_pq[dep[_lca]] = true, qry[dep[_lca]].clear(), pq.push(dep[_lca]);
				qry[dep[_lca]].pb({_lca, k.dis + d[k.v] - d[_lca], k.colour});
			}
		}
	}
	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(long long int, long long int)':
factories.cpp:22:15: warning: variable 'son' set but not used [-Wunused-but-set-variable]
   22 |  int out = 0, son = -1;
      |               ^~~
factories.cpp: In function 'void bl(long long int)':
factories.cpp:69:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |    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:69:100: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |    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:128:6: warning: statement has no effect [-Wunused-value]
  128 |  for(j; pq.size();){
      |      ^
factories.cpp:127:6: warning: unused variable '_p' [-Wunused-variable]
  127 |  int _p = 1e6;
      |      ^~

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