oj.uz

Submission #554149

# Submission time Handle Problem Language Result Execution time Memory
554149 2022-04-27T17:34:30 Z QwertyPi Factories (JOI14_factories) C++14
100 / 100
 7289 ms 223244 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb emplace_back
#define mp make_pair
#pragma pack(1)
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 1 << 20, 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[L][N];
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[0][i] = euler2[i];
	for(int j = 1; j < 20; j++){
		for(int i = 0; i <= n * 2 - 1 - (1 << j); i++){
			st[j][i] = dep[st[j - 1][i]] < dep[st[j - 1][i + (1 << j - 1)]] ? st[j - 1][i] : st[j - 1][i + (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[l][a]] < dep[st[l][b - (1 << l) + 1]] ? st[l][a] : st[l][b - (1 << l) + 1];
	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;
	}
};

ll dp[N][2];

struct cmp{
	bool operator() (const int u, const int v){
		return dep[u] < dep[v];
	}
};

bool in_pq[N];
priority_queue<int, vector<int>, cmp> pq;
vector<int> reach;

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);
	for(int i = 0; i < n; i++){
		dp[i][0] = dp[i][1] = inf;
	}
	for(int i = 0; i < N; i++){
		G[i].resize(0);
	}
	reach.reserve(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;
	for(int j = 0; j < S; j++){
		if(!in_pq[X[j]]) pq.push(X[j]);
		in_pq[X[j]] = true;
	}
	for(int j = 0; j < T; j++){
		if(!in_pq[Y[j]]) pq.push(Y[j]);
		in_pq[Y[j]] = true;
	}
	for(int j = 0; j < S; j++) dp[X[j]][0] = 0;
	for(int j = 0; j < T; j++) dp[Y[j]][1] = 0;
	
	for(int j; pq.size();){
		j = pq.top(); pq.pop(); in_pq[j] = false;
		reach.pb(j);
		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[_lca]) in_pq[_lca] = true, dp[_lca][0] = dp[_lca][1] = inf, pq.push(_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[_lca]) in_pq[_lca] = true, dp[_lca][0] = dp[_lca][1] = inf, pq.push(_lca);
				ll new_dis = dp[j][0] + d[j] - d[_lca];
				ans = min(ans, dp[_lca][1] + new_dis);
				dp[_lca][0] = min(dp[_lca][0], new_dis);
			}
		}
	}
	for(auto i : reach){
		dp[i][0] = dp[i][1] = inf;
	}
	reach.clear();
	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);
	while(pq.size()) pq.pop();
	return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:24:15: warning: variable 'son' set but not used [-Wunused-but-set-variable]
   24 |  int out = 0, son = -1;
      |               ^~~
factories.cpp: In function 'void bl(int)':
factories.cpp:71:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |    st[j][i] = dep[st[j - 1][i]] < dep[st[j - 1][i + (1 << j - 1)]] ? st[j - 1][i] : st[j - 1][i + (1 << j - 1)];
      |                                                           ~~^~~
factories.cpp:71:107: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   71 |    st[j][i] = dep[st[j - 1][i]] < dep[st[j - 1][i + (1 << j - 1)]] ? st[j - 1][i] : st[j - 1][i + (1 << j - 1)];
      |                                                                                                         ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 25704 KB Output is correct
2 Correct 1615 ms 34876 KB Output is correct
3 Correct 2055 ms 34980 KB Output is correct
4 Correct 1458 ms 35036 KB Output is correct
5 Correct 1671 ms 35188 KB Output is correct
6 Correct 1097 ms 34960 KB Output is correct
7 Correct 2009 ms 34980 KB Output is correct
8 Correct 1492 ms 34960 KB Output is correct
9 Correct 1676 ms 35200 KB Output is correct
10 Correct 1087 ms 34872 KB Output is correct
11 Correct 2013 ms 35096 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 25428 KB Output is correct
2 Correct 2681 ms 171196 KB Output is correct
3 Correct 3320 ms 187260 KB Output is correct
4 Correct 1833 ms 189580 KB Output is correct
5 Correct 2398 ms 219976 KB Output is correct
6 Correct 3349 ms 192936 KB Output is correct
7 Correct 3557 ms 74800 KB Output is correct
8 Correct 1730 ms 75528 KB Output is correct
9 Correct 2369 ms 79308 KB Output is correct
10 Correct 3487 ms 76312 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 25704 KB Output is correct
2 Correct 1615 ms 34876 KB Output is correct
3 Correct 2055 ms 34980 KB Output is correct
4 Correct 1458 ms 35036 KB Output is correct
5 Correct 1671 ms 35188 KB Output is correct
6 Correct 1097 ms 34960 KB Output is correct
7 Correct 2009 ms 34980 KB Output is correct
8 Correct 1492 ms 34960 KB Output is correct
9 Correct 1676 ms 35200 KB Output is correct
10 Correct 1087 ms 34872 KB Output is correct
11 Correct 2013 ms 35096 KB Output is correct
12 Correct 18 ms 25428 KB Output is correct
13 Correct 2681 ms 171196 KB Output is correct
14 Correct 3320 ms 187260 KB Output is correct
15 Correct 1833 ms 189580 KB Output is correct
16 Correct 2398 ms 219976 KB Output is correct
17 Correct 3349 ms 192936 KB Output is correct
18 Correct 3557 ms 74800 KB Output is correct
19 Correct 1730 ms 75528 KB Output is correct
20 Correct 2369 ms 79308 KB Output is correct
21 Correct 3487 ms 76312 KB Output is correct
22 Correct 5441 ms 197060 KB Output is correct
23 Correct 3540 ms 199740 KB Output is correct
24 Correct 4681 ms 199828 KB Output is correct
25 Correct 4517 ms 203852 KB Output is correct
26 Correct 7289 ms 199016 KB Output is correct
27 Correct 4660 ms 223244 KB Output is correct
28 Correct 3463 ms 194788 KB Output is correct
29 Correct 6088 ms 198896 KB Output is correct
30 Correct 6128 ms 198184 KB Output is correct
31 Correct 6015 ms 198676 KB Output is correct
32 Correct 2426 ms 81024 KB Output is correct
33 Correct 1737 ms 77328 KB Output is correct
34 Correct 3079 ms 72756 KB Output is correct
35 Correct 3164 ms 72720 KB Output is correct
36 Correct 3167 ms 73340 KB Output is correct
37 Correct 3237 ms 73316 KB Output is correct