oj.uz

Submission #328648

# Submission time Handle Problem Language Result Execution time Memory
328648 2020-11-17T13:04:30 Z MatheusLealV Factories (JOI14_factories) C++17
100 / 100
 7261 ms 190372 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 67564 KB Output is correct
2 Correct 1736 ms 85816 KB Output is correct
3 Correct 1908 ms 85172 KB Output is correct
4 Correct 1746 ms 85572 KB Output is correct
5 Correct 1468 ms 85580 KB Output is correct
6 Correct 1310 ms 85332 KB Output is correct
7 Correct 1912 ms 85228 KB Output is correct
8 Correct 1763 ms 85544 KB Output is correct
9 Correct 1475 ms 85864 KB Output is correct
10 Correct 1317 ms 85356 KB Output is correct
11 Correct 1896 ms 85368 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 67052 KB Output is correct
2 Correct 2609 ms 146204 KB Output is correct
3 Correct 4029 ms 148652 KB Output is correct
4 Correct 1827 ms 143204 KB Output is correct
5 Correct 3259 ms 178680 KB Output is correct
6 Correct 4562 ms 151176 KB Output is correct
7 Correct 4458 ms 102504 KB Output is correct
8 Correct 2052 ms 101804 KB Output is correct
9 Correct 3478 ms 107940 KB Output is correct
10 Correct 4526 ms 103972 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 67564 KB Output is correct
2 Correct 1736 ms 85816 KB Output is correct
3 Correct 1908 ms 85172 KB Output is correct
4 Correct 1746 ms 85572 KB Output is correct
5 Correct 1468 ms 85580 KB Output is correct
6 Correct 1310 ms 85332 KB Output is correct
7 Correct 1912 ms 85228 KB Output is correct
8 Correct 1763 ms 85544 KB Output is correct
9 Correct 1475 ms 85864 KB Output is correct
10 Correct 1317 ms 85356 KB Output is correct
11 Correct 1896 ms 85368 KB Output is correct
12 Correct 40 ms 67052 KB Output is correct
13 Correct 2609 ms 146204 KB Output is correct
14 Correct 4029 ms 148652 KB Output is correct
15 Correct 1827 ms 143204 KB Output is correct
16 Correct 3259 ms 178680 KB Output is correct
17 Correct 4562 ms 151176 KB Output is correct
18 Correct 4458 ms 102504 KB Output is correct
19 Correct 2052 ms 101804 KB Output is correct
20 Correct 3478 ms 107940 KB Output is correct
21 Correct 4526 ms 103972 KB Output is correct
22 Correct 6024 ms 166424 KB Output is correct
23 Correct 5236 ms 165012 KB Output is correct
24 Correct 6069 ms 172536 KB Output is correct
25 Correct 6168 ms 172288 KB Output is correct
26 Correct 7261 ms 161012 KB Output is correct
27 Correct 5079 ms 190372 KB Output is correct
28 Correct 3732 ms 162376 KB Output is correct
29 Correct 7229 ms 159500 KB Output is correct
30 Correct 7120 ms 159144 KB Output is correct
31 Correct 7011 ms 159660 KB Output is correct
32 Correct 3160 ms 112232 KB Output is correct
33 Correct 2409 ms 110080 KB Output is correct
34 Correct 3981 ms 101740 KB Output is correct
35 Correct 3709 ms 101392 KB Output is correct
36 Correct 4347 ms 102328 KB Output is correct
37 Correct 4161 ms 101980 KB Output is correct