oj.uz

Submission #497769

# Submission time Handle Problem Language Result Execution time Memory
497769 2021-12-23T19:00:29 Z S2speed Factories (JOI14_factories) C++17
100 / 100
 3034 ms 227448 KB 
#include<bits/stdc++.h>
#include<factories.h>

using namespace std;

#pragma GCC optimize ("Ofast")

#define all(x) x.begin() , x.end()
#define sze(x) (ll)(x.size())
#define mp(x , y) make_pair(x , y)
#define wall cerr<<"--------------------------------------"<<endl
typedef long long int ll;
typedef pair<ll , ll> pll;
typedef pair<int , int> pii;
typedef long double db;
typedef pair<pll , ll> plll;
typedef pair<int , pii> piii;
typedef pair<pll , pll> pllll;

const ll maxn = 5e5 + 16 , md = 1e9 + 7 , inf = 2e16;

ll n;
vector<pll> adj[maxn] , s , r;
vector<ll> v , vdj[maxn];
bitset<maxn> bl , rd;
ll jad[maxn][20] , dis[maxn] , dep = 0 , st[maxn] , ft[maxn] , tme = 0 , ps[maxn] , sum = 0 , bc[maxn] , rc[maxn];

void pDFS(ll r , ll par){
	st[r] = tme++;
	dis[r] = dep++;
	ps[r] = sum;
	jad[r][0] = par;
	for(ll j = 1 ; j < 20 ; j++){
		if(jad[r][j - 1] == -1) break;
		jad[r][j] = jad[jad[r][j - 1]][j - 1];
	}
	for(auto p : adj[r]){
		ll i = p.first , w = p.second;
		if(i == par) continue;
		sum += w;
		pDFS(i , r);
		sum -= w;
	}
	ft[r] = tme;
	dep--;
	return;
}

ll find_jad(ll v , ll d){
	d = dis[v] - d;
	for(ll j = 0 ; j < 20 ; j++){
		if(d & (1 << j)) v = jad[v][j];
	}
	return v;
}

ll lca(ll v , ll u){
	if(dis[v] > dis[u]) swap(v , u);
	u = find_jad(u , dis[v]);
	if(v == u) return v;
	for(ll j = 19 ; j >= 0 ; j--){
		if(jad[v][j] != jad[u][j]){
			v = jad[v][j];
			u = jad[u][j];
		}
	}
	return jad[v][0];
}

void Init(int N , int v[] , int u[] , int w[]){
	memset(jad , -1 , sizeof(jad));
	memset(bc , 63 , sizeof(bc));
	memset(rc , 63 , sizeof(rc));
	n = N;
	for(ll i = 0 ; i < n - 1 ; i++){
		adj[v[i]].push_back({u[i] , w[i]});
		adj[u[i]].push_back({v[i] , w[i]});
	}
	pDFS(0 , -1);
	return;
}

void cDFS(ll r){
	for(auto i : vdj[r]){
		cDFS(i);
		rc[r] = min(rc[r] , rc[i]);
		bc[r] = min(bc[r] , bc[i]);
	}
	if(rd[r]){
		rc[r] = ps[r];
	} else if(bl[r]){
		bc[r] = ps[r];
	}
	return;
}

ll Query(int k1 , int v1[] , int k2 , int v2[]){
	s.clear(); r.clear(); v.clear();
	for(ll e = 0 ; e < k1 ; e++){
		ll i = v1[e];
		s.push_back({st[i] , i});
		bl[i] = true;
	}
	for(ll e = 0 ; e < k2 ; e++){
		ll i = v2[e];
		s.push_back({st[i] , i});
		rd[i] = true;
	}
	sort(all(s)); r = s;
	ll sz = sze(s);
	for(ll e = 1 ; e < sz ; e++){
		ll i = s[e].second , j = s[e - 1].second , l = lca(i , j);
		r.push_back({st[l] , l});
	}
	sort(all(r));
	r.resize(distance(r.begin() , unique(all(r))));
	ll rs = sze(r);
	for(ll e = 0 ; e < rs ; e++){
		ll i = r[e].second , pr = -1;
		while(!v.empty()){
			ll u = v.back();
			if(st[u] < st[i] && ft[i] <= ft[u]){
				pr = u;
				break;
			}
			v.pop_back();
		}
		if(pr != -1) vdj[pr].push_back(i);
		v.push_back(i);
	}
	cDFS(v[0]);
	ll res = inf;
	for(ll e = 0 ; e < rs ; e++){
		ll i = r[e].second;
		res = min(res , bc[i] + rc[i] - 2ll * ps[i]);
		bc[i] = rc[i] = inf;
		bl[i] = rd[i] = false;
		vdj[i].clear();
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110252 KB Output is correct
2 Correct 827 ms 128280 KB Output is correct
3 Correct 837 ms 128060 KB Output is correct
4 Correct 840 ms 128288 KB Output is correct
5 Correct 714 ms 128316 KB Output is correct
6 Correct 612 ms 128136 KB Output is correct
7 Correct 886 ms 127956 KB Output is correct
8 Correct 797 ms 128280 KB Output is correct
9 Correct 736 ms 128336 KB Output is correct
10 Correct 545 ms 128184 KB Output is correct
11 Correct 855 ms 127956 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 110020 KB Output is correct
2 Correct 1281 ms 182948 KB Output is correct
3 Correct 2065 ms 184472 KB Output is correct
4 Correct 913 ms 180112 KB Output is correct
5 Correct 1817 ms 214976 KB Output is correct
6 Correct 2143 ms 186680 KB Output is correct
7 Correct 1927 ms 143556 KB Output is correct
8 Correct 995 ms 143096 KB Output is correct
9 Correct 1714 ms 149344 KB Output is correct
10 Correct 2081 ms 144836 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 110252 KB Output is correct
2 Correct 827 ms 128280 KB Output is correct
3 Correct 837 ms 128060 KB Output is correct
4 Correct 840 ms 128288 KB Output is correct
5 Correct 714 ms 128316 KB Output is correct
6 Correct 612 ms 128136 KB Output is correct
7 Correct 886 ms 127956 KB Output is correct
8 Correct 797 ms 128280 KB Output is correct
9 Correct 736 ms 128336 KB Output is correct
10 Correct 545 ms 128184 KB Output is correct
11 Correct 855 ms 127956 KB Output is correct
12 Correct 42 ms 110020 KB Output is correct
13 Correct 1281 ms 182948 KB Output is correct
14 Correct 2065 ms 184472 KB Output is correct
15 Correct 913 ms 180112 KB Output is correct
16 Correct 1817 ms 214976 KB Output is correct
17 Correct 2143 ms 186680 KB Output is correct
18 Correct 1927 ms 143556 KB Output is correct
19 Correct 995 ms 143096 KB Output is correct
20 Correct 1714 ms 149344 KB Output is correct
21 Correct 2081 ms 144836 KB Output is correct
22 Correct 2684 ms 199784 KB Output is correct
23 Correct 2302 ms 201700 KB Output is correct
24 Correct 2999 ms 204040 KB Output is correct
25 Correct 3023 ms 207480 KB Output is correct
26 Correct 3016 ms 194644 KB Output is correct
27 Correct 2797 ms 227448 KB Output is correct
28 Correct 1413 ms 198044 KB Output is correct
29 Correct 2929 ms 193828 KB Output is correct
30 Correct 2973 ms 193424 KB Output is correct
31 Correct 3034 ms 193864 KB Output is correct
32 Correct 1394 ms 154796 KB Output is correct
33 Correct 945 ms 148980 KB Output is correct
34 Correct 1557 ms 142088 KB Output is correct
35 Correct 1520 ms 142148 KB Output is correct
36 Correct 1771 ms 142852 KB Output is correct
37 Correct 1714 ms 142892 KB Output is correct