Submission #328648

#	Time	Username	Problem	Language	Result	Execution time	Memory
328648		MatheusLealV	Factories (JOI14_factories)	C++17	100 / 100	7261 ms	190372 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define f first
#define s second
#define N 500020
#define pb push_back
#define logn 20
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
typedef long long ll;
using namespace std;
typedef pair<ll, ll> pii;
typedef vector<int> vi;

vector<pii> grafo[N];
int n, q, in[N];

struct edge{	
	int a, b;
	ll c;
};

struct binarylift{
	int anc[N][logn], deep[N], cnt;
	ll distt[N];
	void dfs(int x, int p){
		in[x] = ++cnt;
		anc[x][0] = p;
		deep[x] = deep[p] + 1;
		for(auto v: grafo[x]){
			if(v.f == p) continue;
			distt[v.f] =distt[x] + 1LL*v.s;
			dfs(v.f, x);	
		}
	}
	int lca(int u, int v){
	    if(deep[v] > deep[u]) swap(u, v);
	    for(int i = logn - 1; i>=0; i--)
	        if(deep[u] - (1<<i) >= deep[v]) u = anc[u][i];
	    if(u == v){
	    	return u;
	    }
	    for(int i = logn - 1; i>=0; i--)
		    if(anc[u][i] != -1 & anc[u][i] != anc[v][i]){
		       u = anc[u][i];
		       v = anc[v][i];
		    }
	    return anc[u][0];
	}
	void solve(){
		memset(anc, -1, sizeof anc);
		dfs(1, 1);
		for(int j = 1; j < logn; j++)
			for(int i = 1; i <= n; i++)
				anc[i][j] = anc[anc[i][j-1]][j-1];
	}
	ll dist(int a, int b){
		return distt[a]+distt[b]-2*distt[lca(a,b)];
	}
} b;

pair<vector<edge> ,int> build_virtual_tree(vi K){
    auto f = [&](int a , int b){
        return in[a] < in[b];
    };
    vector<edge> e;
    sort(all(K) , f);
    int m = sz(K);
    rep(i,1,m){
        K.push_back(b.lca(K[i] , K[i-1]));
    }
    sort(all(K) , f);
    K.erase(unique(all(K)) , K.end());
    rep(i,0,sz(K) -1){
        int z = b.lca(K[i] , K[i+1]);
        e.push_back({K[i+1] , z ,b.dist(z,K[i+1])});
    }
    return {e ,K[0]};
}
ll dist[N];
void Init(int NN, int A[], int B[], int D[]) {
	n=NN;
	for(int i = 0; i < N; i++) dist[i] = (ll)(2e18);
	for(int i = 0; i < n - 1; i++){
		int a = A[i], b = B[i];
		ll c = D[i];
		a++,b++;
		grafo[a].pb({b, c});
		grafo[b].pb({a, c});
	}
	b.solve();
}

vector< pii > tree[N];
ll Query(int S, int X[], int T, int Y[]) {
	vector<int> caras;
	for(int i =0;i<S;i++){
		X[i] ++;
		caras.pb(X[i]);
	}
	for(int i =0;i<T;i++){
		Y[i] ++;
		caras.pb(Y[i]);
	}
	sort(all(caras));
	caras.erase(unique(all(caras)), caras.end());

	auto t = build_virtual_tree(caras);
	for(auto w: t.f){
		int a = w.a, b=w.b;
		ll c=w.c;
		tree[a].pb({b, c});
		tree[b].pb({a, c});
		caras.pb(a);
		caras.pb(b);
	}
	const ll inf = (ll)(2e18);
	priority_queue<pii, vector<pii>, greater<pii> > pq;
	for(int i = 0; i < S; i++){
		dist[X[i]] = 0, pq.push({0, X[i]});
	}
	while(!pq.empty()){
		int x = pq.top().s;
		ll d= pq.top().f;
		pq.pop();
		if(d>dist[x])continue;
		for(auto v: tree[x]){
			if(dist[v.f] > dist[x] + v.s){
				dist[v.f] = dist[x] + v.s;
				pq.push({dist[v.f], v.f});
			}
		}
	}

	ll ans = inf;
	for(int i = 0; i < T; i++) ans = min(ans, dist[Y[i]]);
	for(auto x: caras){
		dist[x] = inf;
		tree[x].clear();
	}
	return ans;
}

Compilation message (stderr)

factories.cpp: In member function 'int binarylift::lca(int, int)':
factories.cpp:45:20: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   45 |       if(anc[u][i] != -1 & anc[u][i] != anc[v][i]){
      |          ~~~~~~~~~~^~~~~

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