Submission #26550

#	Time	Username	Problem	Language	Result	Execution time	Memory
26550		rubabredwan	Factories (JOI14_factories)	C++14	15 / 100	6000 ms	207376 KiB

factories

/*  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 < vector <int>> g(N), cost(N);
int n;
int tot;
int sub[N];
int anc[N];
int vis[N];
int lst[N], t;
long long mn[N];
long long pre[N][25];
int idx[N];
 
inline void dfs0(int at, int par){
	++tot;
	sub[at] = 1;
	for(int i = 0; i < g[at].size(); ++i){
		if(vis[g[at][i]] || g[at][i] == par) continue;
		dfs0(g[at][i], at);
		sub[at] += sub[g[at][i]];
	}
}
 
inline int get(int at, int par){
	for(int i = 0; i < g[at].size(); ++i){
		if(vis[g[at][i]] || g[at][i] == par) continue;
		if(sub[g[at][i]] > tot / 2) return get(g[at][i], at);
	}
	return at;
}
 
inline void get_dis(int at, int par, long long dis){
	pre[at][++idx[at]] = dis;
	for(int i = 0; i < g[at].size(); ++i){
		if(vis[g[at][i]] || g[at][i] == par) continue;
		get_dis(g[at][i], at, dis + cost[at][i]);
	}
}
 
inline void decompose(int at, int par){
	tot = 0;
	dfs0(at, at);
	int cen = get(at, at);
	vis[cen] = 1;
	if(par) anc[cen] = par;
	get_dis(cen, cen, 0);
	for(int i = 0; i < g[cen].size(); ++i){
		if(!vis[g[cen][i]]) decompose(g[cen][i], cen);
	}
}
 
inline void update(int from){
	int cur = from;
	for(int i = idx[from]; i >= 1; --i){
		if(lst[cur] == t) mn[cur] = min(mn[cur], pre[from][i]);
		else lst[cur] = t, mn[cur] = pre[from][i];
		cur = anc[cur];
	}
}
 
inline long long query(int from){
	int cur = from;
	long long ret = oo;
	for(int i = idx[from]; i >= 1; --i){
		if(lst[cur] == t) ret = min(ret, mn[cur] + pre[from][i]);
		cur = anc[cur];
	}
	return ret;
}
 
long long Query(int S, int X[], int T, int Y[]){
	++t;
	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 - 1; ++i){
		g[A[i] + 1].push_back(B[i] + 1);
		g[B[i] + 1].push_back(A[i] + 1);
		cost[A[i] + 1].push_back(D[i]);
		cost[B[i] + 1].push_back(D[i]);
	}
	decompose(1, 0);
	for(int i = 1; i <= n; ++i) mn[i] = oo;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs0(int, int)':
factories.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[at].size(); ++i){
                   ^
factories.cpp: In function 'int get(int, int)':
factories.cpp:35:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[at].size(); ++i){
                   ^
factories.cpp: In function 'void get_dis(int, int, long long int)':
factories.cpp:44:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[at].size(); ++i){
                   ^
factories.cpp: In function 'void decompose(int, int)':
factories.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[cen].size(); ++i){
                   ^

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