Submission #770944

#	Time	Username	Problem	Language	Result	Execution time	Memory
770944		minhcool	Factories (JOI14_factories)	C++17	100 / 100	5400 ms	246512 KiB

factories

#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 (stderr)

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 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67