Submission #287490

#	Time	Username	Problem	Language	Result	Execution time	Memory
287490		limabeans	Factories (JOI14_factories)	C++17	15 / 100	8031 ms	411044 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl


using ll = long long;
const ll inf = 1e18;

const ll mod = 1e9+7;
const int maxn = 1e6+10;

vector<pair<ll,int>> g[maxn];
const int LOG = 19;
int par[maxn][LOG+1];
int dep[maxn];
ll depw[maxn];
int n;
int cloc = 0;
int tin[maxn];
vector<pair<int,int>> ett;

struct sparse_table {

    int LOG = 0;
    int n;
    vector<pair<int,int>> a[100];
    vector<int> lg_floor;

    pair<int,int> eval(pair<int,int> x, pair<int,int> y) {
	return min(x, y);
    }

    void init(vector<pair<int,int>> v) {
	n = v.size();
	LOG = 0;
	while ((1<<LOG) <= n) LOG++;
	lg_floor.resize(n+10);
	lg_floor[1] = 0;
	for (int i=2; i<n+10; i++) lg_floor[i] = 1 + lg_floor[i/2];
	for (int j=0; j<LOG; j++) a[j].resize(n);
	for (int i=0; i<n; i++) a[0][i] = v[i];
	

	for (int j=1; j<LOG; j++) {
	    for (int i=0; i<n; i++) {
		a[j][i] = a[j-1][i];
		if (i + (1<<(j-1)) < n) {
		    a[j][i] = eval(a[j][i], a[j-1][i + (1<<(j-1))]);
		}
	    }
	}
    }

    pair<int,int> get(int l, int r) {
	assert(l<=r);
	int lg = lg_floor[r - l + 1];

	return eval(a[lg][l], a[lg][r-(1<<lg)+1]);
	
    }
};

sparse_table tbl;

void dfs(int at, int p) {
    tin[at] = cloc++;
    ett.push_back({tin[at], at});

    
    if (~p) {
	for (int j=1; j<LOG; j++) {
	    par[at][j] = par[par[at][j-1]][j-1];
	}
    }
    for (auto ed: g[at]) {
	int to = ed.second;
	if (to == p) continue;
	par[to][0] = at;
	dep[to] = 1+dep[at];
	depw[to] = ed.first+depw[at];
	dfs(to, at);
	ett.push_back({tin[at], at});
	cloc++;
    }

    ett.push_back({tin[at], at});
    cloc++;
}


int lca(int u, int v) {
    if (u==v) return u;
    int lo = tin[u];
    int hi = tin[v];
    if (lo>hi) swap(lo, hi);
    pair<int,int> res = tbl.get(lo, hi);
    return res.second;
}

int lcaBrute(int u, int v) {
    if (dep[u]<dep[v]) swap(u, v);
    int dx = dep[u]-dep[v];

    for (int j=0; j<LOG; j++) {
	if (dx>>j&1) {
	    u=par[u][j];
	}
    }
    
    if (u==v) return v;

    for (int j=LOG-1; j>=0; j--) {
	if (par[u][j] != par[v][j]) {
	    u=par[u][j];
	    v=par[v][j];
	}
    }
    return par[v][0];
}



ll dist(int u, int v) {
    if (u==v) return 0;
    int mid = lca(u,v);
    return depw[u]+depw[v]-2ll*depw[mid];
}


void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i=0; i<N-1; i++) {
	g[A[i]].push_back({D[i],B[i]});
	g[B[i]].push_back({D[i],A[i]});
    }

    dfs(0, -1);
    tbl.init(ett);
}





ll QuerySmall(int S, int X[], int T, int Y[]) {
    ll res = inf;
    for (int i=0; i<S; i++) {
	for (int j=0; j<T; j++) {
	    //cout<<X[i]<<","<<Y[j]<<endl;
	    res = min(res, dist(X[i],Y[j]));
	}
    }
    return res;
}

ll dp[maxn];
bool dest[maxn];


long long Query(int S, int X[], int T, int Y[]) {

    if (S<=10 && T<=10) {
	return QuerySmall(S, X, T, Y);
    }
    
    for (int i=0; i<n; i++) {
	dp[i] = inf;
	dest[i] = false;
    }
    for (int i=0; i<S; i++) {
	dp[X[i]] = 0;
    }
    for (int i=0; i<T; i++) {
	dest[Y[i]] = true;
    }
    priority_queue<pair<ll,int>,vector<pair<ll,int>>,greater<pair<ll,int>>> pq;
    for (int i=0; i<S; i++) {
	pq.push({0, X[i]});
    }


    while (pq.size()) {
	auto cur = pq.top();
	pq.pop();
	int at = cur.second;
	ll len = cur.first;
	if (len > dp[at]) {
	    continue;
	}
	if (dest[at]) {
	    return len;
	}
	for (auto ed: g[at]) {
	    int to = ed.second;
	    ll wei = ed.first;
	    if (len+wei < dp[to]) {
		dp[to] = len+wei;
		pq.push({dp[to], to});
	    }
	}
    }

    ll res = inf;
    for (int i=0; i<T; i++) {
	res = min(res, dp[Y[i]]);
    }

    
    return res;
}

int q;
int a[maxn], b[maxn], d[maxn];
int x[maxn], y[maxn];

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