oj.uz

Submission #287488

# Submission time Handle Problem Language Result Execution time Memory
287488 2020-08-31T17:51:09 Z limabeans Factories (JOI14_factories) C++17
15 / 100
 1902 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 24448 KB Output is correct
2 Correct 511 ms 35300 KB Output is correct
3 Correct 530 ms 35192 KB Output is correct
4 Correct 535 ms 35564 KB Output is correct
5 Correct 499 ms 35704 KB Output is correct
6 Correct 579 ms 35436 KB Output is correct
7 Correct 537 ms 35372 KB Output is correct
8 Correct 1331 ms 35604 KB Output is correct
9 Correct 499 ms 35484 KB Output is correct
10 Correct 586 ms 35636 KB Output is correct
11 Correct 535 ms 35320 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 1902 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 24448 KB Output is correct
2 Correct 511 ms 35300 KB Output is correct
3 Correct 530 ms 35192 KB Output is correct
4 Correct 535 ms 35564 KB Output is correct
5 Correct 499 ms 35704 KB Output is correct
6 Correct 579 ms 35436 KB Output is correct
7 Correct 537 ms 35372 KB Output is correct
8 Correct 1331 ms 35604 KB Output is correct
9 Correct 499 ms 35484 KB Output is correct
10 Correct 586 ms 35636 KB Output is correct
11 Correct 535 ms 35320 KB Output is correct
12 Correct 19 ms 24320 KB Output is correct
13 Runtime error 1902 ms 524288 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -