oj.uz

Submission #422341

# Submission time Handle Problem Language Result Execution time Memory
422341 2021-06-10T03:49:39 Z amunduzbaev Factories (JOI14_factories) C++14
0 / 100
 35 ms 12492 KB 
#include "factories.h"

#ifndef EVAL
#include "grader.cpp"
#endif

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

#define pb push_back
#define ff first
#define ss second
#define pii pair<int, int>
#define ll long long
#define sz(x) (int)x.size()

template<class T> bool umin(T& a, const T b) { if(a > b) { a = b; return 1; } return 0; }
template<class T> bool umax(T& a, const T b) { if(a < b) { a = b; return 1; } return 0; }

const int MAXN = 5e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;

vector<pii> edges[MAXN], ss;
int n, tin[MAXN], tout[MAXN], t, lg[MAXN];
pii st[MAXN*2][20];
ll dep[MAXN];

void dfs(int u, int p = -1){
	ss.pb({dep[u], u});
	tin[u] = sz(ss)-1;
	for(auto x : edges[u]){
		if(x.ff == p) continue;
		dep[x.ff] = dep[u] + (ll)x.ss;
		dfs(x.ff, u);
		ss.pb({dep[u], u});
	} tout[u] = sz(ss)-1;
}

void Init(int n, int a[], int b[], int d[]) {
	for(int i=0;i<n-1;i++){ // a[i]++, b[i]++;
		edges[a[i]].pb({b[i], d[i]}), edges[b[i]].pb({a[i], d[i]}); 
	} dfs(0); 
	lg[1] = 0;
	for(int i=2;i<=n;i++) lg[i] = lg[i/2]+1;
	for(int i=0;i<sz(ss);i++) st[i][0] = ss[i];
	for(int j=1;j<20;j++){
		for(int i=0;i<sz(ss);i++){
			if(i + (1<<(j - 1)) < sz(ss)) st[i][j] = min(st[i][j-1], st[i+(1<<(j-1))][j-1]);
			else st[i][j] = st[i][j-1];
		}
	}
}

bool par(int a, int b) { return (tin[a] <= tin[b] && tout[a] >= tout[b]); }

int find_lca(int a, int b){
	if(par(a, b)) return a;
	if(par(b, a)) return b;
	if(tin[a] > tout[b]) swap(a, b);
	int l = tout[a], r = tin[b], llg = lg[r-l+1];
	pii mn = min(st[l][llg], st[r-(1<<llg)][llg]);
	return mn.ss;
}

ll Query(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++){
			int a = x[i], b = y[j]; // a++, b++;
			int lca = find_lca(a, b);
			umin(res, dep[a] + dep[b] - dep[lca] * 2);
		}
	} return res;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 12492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 12364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 12492 KB Output isn't correct
2 Halted 0 ms 0 KB -