oj.uz

Submission #26543

# Submission time Handle Problem Language Result Execution time Memory
26543 2017-07-02T16:53:09 Z rubabredwan Factories (JOI14_factories) C++14
0 / 100
 6000 ms 122700 KB 
/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>
#include "factories.h"

using namespace std;

typedef pair <int, long long> pii;

const int N = 500005;
const long long oo = 1e18;

vector <pii> g[N];
int n;
int tot;
int sub[N];
int anc[N];
int vis[N];
int pa[N][20];
long long dep[N];
long long level[N];
long long mn[N];
stack <int> rem;

void dfs(int at, int par){
	pa[at][0] = par;
	for(int i = 1; i <= 18; ++i) pa[at][i] = pa[ pa[at][i-1] ][ i-1 ];
	for(auto u : g[at]){
		if(u.first != par){
			dep[u.first] = dep[at] + u.second;
			level[u.first] = level[at] + 1;
			dfs(u.first, at);
		}
	}
}

int lca(int a, int b){
	if(level[a] < level[b]) swap(a, b);
	for(int i = 18; i >= 0; --i) if(level[a] - (1 << i) >= level[b]) a = pa[a][i];
	if(a == b) return a;
	for(int i = 18; i >= 0; --i) if(pa[a][i] != pa[b][i]) a = pa[a][i], b = pa[b][i];
	return pa[a][0];
}

long long dis(int a, int b){
	int lc = lca(a, b);
	return dep[a] + dep[b] - 2LL * dep[lc];
}

void dfs0(int at, int par){
	++tot;
	sub[at] = 1;
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		dfs0(u.first, at);
		sub[at] += sub[u.first];
	}
}

int get(int at, int par){
	for(auto u : g[at]){
		if(vis[u.first] || u.first == par) continue;
		if(sub[u.first] > tot / 2) return get(u.first, at);
	}
	return at;
}

void decompose(int at, int par){
	tot = 0;
	dfs0(at, at);
	int cen = get(at, at);
	vis[cen] = 1;
	if(par){ 
		anc[cen] = par;
	}
	for(auto u : g[cen]){
		if(vis[u.first]) continue;
		decompose(u.first, cen);
	}
}

void update(int from){
	int cur = from;
	int cnt = 0;
	while(cur){
		mn[cur] = min(mn[cur], dis(cur, from));
		rem.push(cur);
		cur = anc[cur];
		++cnt;
		if(cnt >= 100) assert(0);
	}
}

long long query(int from){
	int cur = from;
	long long ret = oo;
	int cnt = 0;
	while(cur){
		ret = min(ret, dis(cur, from) + mn[cur]);
		cur = anc[cur];
		++cnt;
		if(cnt >= 100) assert(0);
	}
	return ret;
}

void reset(){
	while(!rem.empty()){
		mn[rem.top()] = oo;
		rem.pop();
	}
}

long long Query(int S, int X[], int T, int Y[]){
	reset();
	for(int i = 0; i < S; ++i){
		update(X[i] + 1);
	}	
	long long ret = oo;
	for(int i = 0; i < T; ++i){
		ret = min(ret, query(Y[i] + 1));
	}
	return ret;
}

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 92652 KB Output is correct
2 Correct 1216 ms 92916 KB Output is correct
3 Runtime error 353 ms 92920 KB Execution killed because of forbidden syscall gettid (186)
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 92652 KB Output is correct
2 Correct 5066 ms 118260 KB Output is correct
3 Execution timed out 6000 ms 122700 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6000 ms 120524 KB Execution timed out
2 Halted 0 ms 0 KB -