Submission #57683

#	Time	Username	Problem	Language	Result	Execution time	Memory
57683		Benq	Factories (JOI14_factories)	C++14	15 / 100	5331 ms	525312 KiB

factories

#include "factories.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500005;

template<class T, int SZ> struct RMQ {
    T stor[SZ][32-__builtin_clz(SZ)];
    
    T comb(T a, T b) {
        return min(a,b);
    }
    
    void build(vector<T>& x) {
        F0R(i,sz(x)) stor[i][0] = x[i];
        FOR(j,1,32-__builtin_clz(SZ)) F0R(i,SZ-(1<<(j-1))) 
            stor[i][j] = comb(stor[i][j-1],
                        stor[i+(1<<(j-1))][j-1]);
    }
    
    T query(int l, int r) {
        int x = 31-__builtin_clz(r-l+1);
        return comb(stor[l][x],stor[r-(1<<x)+1][x]);
    }
};

template<int SZ> struct LCA {
    vpi edges[SZ];
    RMQ<pl,2*SZ> r;
    vpl tmp;
    ll depth[SZ];
    int pos[SZ];
    
    int V, R;
    
    void addEdge(int u, int v, int d) {
        edges[u].pb({v,d}), edges[v].pb({u,d});
    }
    
    void dfs(int u, int prev){
        pos[u] = sz(tmp);
        tmp.pb({depth[u],u});
        for (pi v: edges[u]) if (v.f != prev) {
        	depth[v.f] = depth[u]+v.s;
            dfs(v.f, u);
            tmp.pb({depth[u],u});
        }
    }
    
    void construct() {
        dfs(R, 0);
        r.build(tmp);
    }
    
    int lca(int u, int v){
        u = pos[u], v = pos[v];
        if (u > v) swap(u,v);
        return r.query(u,v).s;
    }
    
    ll dist(int u, int v) {
        return depth[u]+depth[v]-2*depth[lca(u,v)];
    }
};

LCA<MX> L;

template<int SZ> struct Dijkstra {
    ll dist[SZ];
    vector<pi> adj[SZ];
    
    void addEdge(int a, int b, int d) {
    	adj[a].pb({b,d}), adj[b].pb({a,d});
    }

    void gen(int S, int X[]) {
    	F0R(i,L.V) dist[i] = INF;
    	priority_queue<pl,vector<pl>,greater<pl>> q;

    	F0R(i,S) {
    		dist[X[i]] = 0;
    		q.push({0,X[i]});
    	}
	
    	while (q.size()) {
    		pl x = q.top(); q.pop();
    		if (dist[x.s] < x.f) continue;
    		for (pi y: adj[x.s]) if (x.f+y.s < dist[y.f]) {
    			dist[y.f] = x.f+y.s;
    			q.push({dist[y.f],y.f});
    		}
    	}
    }
};

Dijkstra<MX> Di;

void Init(int N, int A[], int B[], int D[]) {
	L.V = N, L.R = 0;
	F0R(i,N-1) {
		L.addEdge(A[i],B[i],D[i]);
		Di.addEdge(A[i],B[i],D[i]);
	}
	L.construct();
}

long long Query(int S, int X[], int T, int Y[]) {
	ll ans = INF;
	if ((ll)S*T > L.V) {
		Di.gen(S,X);
		F0R(i,T) ans = min(ans,Di.dist[Y[i]]);
	} else {
		F0R(i,S) F0R(j,T) ans = min(ans,L.dist(X[i],Y[j]));
	}
	return ans;
}

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