oj.uz

Submission #770944

# Submission time Handle Problem Language Result Execution time Memory
770944 2023-07-02T07:33:17 Z minhcool Factories (JOI14_factories) C++17
100 / 100
 5400 ms 246512 KB 
#include<bits/stdc++.h>
//#include "factories.h"
using namespace std;
 
#define ll long long
#define fi first
#define se second
#define pb push_back
 
typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;
 
const ll N = 5e5 + 5, oo = 1e18 + 7, mod = 1e9 + 7;
 
ll n;
vector<pair<ll, ll>> Adj[N];
 
ll d1[N], d2[N];
 
ll anc[N][20];
 
void dfs(ll u, ll p){
    for(auto it : Adj[u]){
        ll v = it.fi, w = it.se;
        if(v == p) continue;
        d1[v] = d1[u] + 1;
        d2[v] = d2[u] + w;
        anc[v][0] = u;
        //dist[v][0] = w;
        dfs(v, u);
    }
}
 
void prep(){
    for(ll i = 1; i <= 19; i++){
        for(ll j = 1; j <= n; j++){
            anc[j][i] = anc[anc[j][i - 1]][i - 1];
            //dist[j][i] = dist[j][i - 1] + dist[anc[j][i - 1]][i - 1];
        }
    }
}
 
ll lca(ll x, ll y){
    if(d1[x] > d1[y]) swap(x, y);
    for(ll i = 19; i >= 0; i--){
        if((d1[x] + (1LL << i)) <= d1[y]) y = anc[y][i];
    }
    if(x == y) return x;
    for(ll i = 19; i >= 0; i--){
        if(anc[x][i] != anc[y][i]){
            x = anc[x][i], y = anc[y][i];
        }
    }
    return anc[x][0];
}
 
ll dist(ll x, ll y){
    return d2[x] + d2[y] - 2 * d2[lca(x, y)];
}
 
ll cnt;
ll pos[N], l[N], r[N];
ll arr[N];
 
void pre_dfs(ll u, ll p){
    cnt++;
    pos[u] = l[u] = cnt;
    arr[cnt] = u;
    for(auto it : Adj[u]){
        ll v = it.fi;
        if(v == p) continue;
        pre_dfs(v, u);
    }
    r[u] = cnt;
}
 
void Init(int N, int A[], int B[], int D[]){
    n = N;
    for(ll i = 0; i < (n - 1); i++){
        Adj[A[i] + 1].pb({B[i] + 1, D[i]});
        Adj[B[i] + 1].pb({A[i] + 1, D[i]});
    }
    pre_dfs(1, 1);
    dfs(1, 1);
    prep();
}

bool cmp(ll a, ll b){
	return l[a] < l[b];
}

ll type[N];

pair<ll, ll> mini[N];

vector<pair<ll, ll>> Adj2[N];

void dfs3(ll u){
	mini[u] = {oo, oo};
	if(type[u] == 1) mini[u].fi = 0;
	if(type[u] == 2) mini[u].se = 0;
	for(auto it : Adj2[u]){
		ll v = it.fi, w = it.se;
		dfs3(v);
		mini[u].fi = min(mini[u].fi, mini[v].fi + w);
		mini[u].se = min(mini[u].se, mini[v].se + w);
	}
}
 
ll Query(int S, int X[], int T, int Y[]){
	//return 0;
	vector<ll> vc;
    for(ll i = 0; i < S; i++){
    	vc.pb(X[i] + 1);
    	type[X[i] + 1] = 1;
	}
	for(ll i = 0; i < T; i++){
		vc.pb(Y[i] + 1);
		type[Y[i] + 1] = 2;
	}
 //   for(ll i = 0; i < T; i++) vc.pb(Y[i] + 1);
    sort(vc.begin(), vc.end(), cmp);
    vector<ll> nodes;
    for(auto it : vc) nodes.pb(it);
    for(ll i = 0; (i + 1) < vc.size(); i++){
    	ll temp = lca(vc[i], vc[i + 1]);
    	nodes.pb(temp);
	}
	sort(nodes.begin(), nodes.end(), cmp);
	nodes.resize(unique(nodes.begin(), nodes.end()) - nodes.begin());
	set<iii> se;
	ll root;
	for(auto it : nodes){
		set<iii>::iterator it2 = se.lower_bound({{r[it], -oo}, -oo});
		if(it2 != se.end()){
		//	cout << it << " " << (*it2).se << "\n";
			Adj2[((*it2).se)].pb({it, dist(it, (*it2).se)});
		} 
		else root = it;
		se.insert({{r[it], r[it] - l[it] + 1}, it});
	}
	//return 0;
	dfs3(root);
	ll answer = oo;
	for(auto it : nodes) answer = min(answer, mini[it].fi + mini[it].se);
	for(auto it : nodes) Adj2[it].clear();
	//sort(nodes.begin(), nodes.end(), greater<ii>());
	for(auto it : nodes) type[it] = 0;
	return answer;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:126:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for(ll i = 0; (i + 1) < vc.size(); i++){
      |                   ~~~~~~~~^~~~~~~~~~~
factories.cpp:144:6: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
  144 |  dfs3(root);
      |  ~~~~^~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24512 KB Output is correct
2 Correct 1346 ms 43180 KB Output is correct
3 Correct 1447 ms 43052 KB Output is correct
4 Correct 1373 ms 43528 KB Output is correct
5 Correct 1006 ms 43412 KB Output is correct
6 Correct 810 ms 43048 KB Output is correct
7 Correct 1427 ms 42960 KB Output is correct
8 Correct 1372 ms 43432 KB Output is correct
9 Correct 1042 ms 43408 KB Output is correct
10 Correct 838 ms 43064 KB Output is correct
11 Correct 1421 ms 43060 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24148 KB Output is correct
2 Correct 1820 ms 194548 KB Output is correct
3 Correct 2955 ms 198292 KB Output is correct
4 Correct 1183 ms 191696 KB Output is correct
5 Correct 2552 ms 233320 KB Output is correct
6 Correct 3202 ms 200252 KB Output is correct
7 Correct 2525 ms 77260 KB Output is correct
8 Correct 1056 ms 76664 KB Output is correct
9 Correct 2206 ms 83664 KB Output is correct
10 Correct 2473 ms 78684 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 24512 KB Output is correct
2 Correct 1346 ms 43180 KB Output is correct
3 Correct 1447 ms 43052 KB Output is correct
4 Correct 1373 ms 43528 KB Output is correct
5 Correct 1006 ms 43412 KB Output is correct
6 Correct 810 ms 43048 KB Output is correct
7 Correct 1427 ms 42960 KB Output is correct
8 Correct 1372 ms 43432 KB Output is correct
9 Correct 1042 ms 43408 KB Output is correct
10 Correct 838 ms 43064 KB Output is correct
11 Correct 1421 ms 43060 KB Output is correct
12 Correct 15 ms 24148 KB Output is correct
13 Correct 1820 ms 194548 KB Output is correct
14 Correct 2955 ms 198292 KB Output is correct
15 Correct 1183 ms 191696 KB Output is correct
16 Correct 2552 ms 233320 KB Output is correct
17 Correct 3202 ms 200252 KB Output is correct
18 Correct 2525 ms 77260 KB Output is correct
19 Correct 1056 ms 76664 KB Output is correct
20 Correct 2206 ms 83664 KB Output is correct
21 Correct 2473 ms 78684 KB Output is correct
22 Correct 4579 ms 219832 KB Output is correct
23 Correct 3951 ms 222008 KB Output is correct
24 Correct 5049 ms 226612 KB Output is correct
25 Correct 5061 ms 230228 KB Output is correct
26 Correct 5400 ms 209052 KB Output is correct
27 Correct 4581 ms 246512 KB Output is correct
28 Correct 2515 ms 213036 KB Output is correct
29 Correct 5329 ms 207644 KB Output is correct
30 Correct 5361 ms 207156 KB Output is correct
31 Correct 5350 ms 207520 KB Output is correct
32 Correct 2329 ms 92080 KB Output is correct
33 Correct 1474 ms 85196 KB Output is correct
34 Correct 2169 ms 76392 KB Output is correct
35 Correct 2194 ms 76144 KB Output is correct
36 Correct 2705 ms 77000 KB Output is correct
37 Correct 2678 ms 76844 KB Output is correct