oj.uz

Submission #287489

# Submission time Handle Problem Language Result Execution time Memory
287489 2020-08-31T17:54:56 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 1914 ms 524288 KB 
#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 {

    const static int LOG = 19;
    int n;
    vector<pair<int,int>> a[LOG+1];
    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();
	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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24696 KB Output is correct
2 Correct 505 ms 36240 KB Output is correct
3 Correct 537 ms 36600 KB Output is correct
4 Correct 528 ms 36844 KB Output is correct
5 Correct 493 ms 36984 KB Output is correct
6 Correct 580 ms 36788 KB Output is correct
7 Correct 531 ms 36344 KB Output is correct
8 Correct 1329 ms 36472 KB Output is correct
9 Correct 491 ms 36600 KB Output is correct
10 Correct 584 ms 36404 KB Output is correct
11 Correct 547 ms 36416 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24320 KB Output is correct
2 Runtime error 1914 ms 524288 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 24696 KB Output is correct
2 Correct 505 ms 36240 KB Output is correct
3 Correct 537 ms 36600 KB Output is correct
4 Correct 528 ms 36844 KB Output is correct
5 Correct 493 ms 36984 KB Output is correct
6 Correct 580 ms 36788 KB Output is correct
7 Correct 531 ms 36344 KB Output is correct
8 Correct 1329 ms 36472 KB Output is correct
9 Correct 491 ms 36600 KB Output is correct
10 Correct 584 ms 36404 KB Output is correct
11 Correct 547 ms 36416 KB Output is correct
12 Correct 19 ms 24320 KB Output is correct
13 Runtime error 1914 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -