Submission #38080

#	Time	Username	Problem	Language	Result	Execution time	Memory
38080		MatheusLealV	Factories (JOI14_factories)	C++14	15 / 100	5883 ms	268940 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
#define Ni 500050
#define logn 20
#define inf 200000000000000000
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int n, q, nivel[Ni], block[Ni], sz[Ni], tot, pai[Ni], root, tmp = 1, ini[Ni], deep[2*Ni];

ll dist[Ni], ans[Ni];

vector<pii> grafo[Ni];

vector<int> tree[Ni], euler;

pii best, dp[2*Ni][logn];

int last_upd[Ni], cnt_upd = 1;

inline void build()
{
  for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(deep[i], euler[i]);

  for(int j = 1; j < logn; j++)
  {
      for(int i = 0; i < euler.size(); i++)
      {
      	if(i + (1<<(j - 1) < 2*Ni)) dp[i][j] = min(dp[i][j - 1], dp[ i + (1<<(j - 1)) ][j - 1]);

      	else dp[i][j] = dp[i][j - 1];
   	  }
  }
}

inline int query(int l, int r)
{
	if(l == r) return euler[l];

	int e = 31-__builtin_clz(r-l);

	return min(dp[l][e], dp[r - (1<<e) + 1][e]).s;
}

inline void dfs(int x, int p)
{
	if(ini[x] == 0) ini[x] = tmp;

	euler.push_back(x);

	tmp ++;

	for(int i = 0; i < grafo[x].size(); i++)
	{
		int v = grafo[x][i].f;

		ll peso = (ll)grafo[x][i].s;

		if(v == p) continue;

		nivel[v] = nivel[x] + 1;

		dist[v] = dist[x] + peso;

		dfs(v, x);

		euler.push_back(x);

		tmp ++;
	}
}

inline void init()
{
	dfs(1, 1);

	for(int i = 0; i < euler.size(); i++) deep[i] = nivel[euler[i]];

	build();
}

inline int lca(int a, int b)
{
	return query(min(ini[a] - 1, ini[b] - 1), max(ini[a] - 1, ini[b] - 1));
}

inline int tam(int x, int p)
{
    sz[x] = 1;

    for(int i = 0; i < grafo[x].size(); i++)
    {
        int v = grafo[x][i].f;

        if(v == p || block[v]) continue;

        sz[x] += tam(v, x);
    }

    return sz[x];
}

inline void split(int x, int p)
{
    int maior = tot - sz[x];

    for(int i = 0; i < grafo[x].size(); i++)
    {
         int v = grafo[x][i].f;

         if(v == p || block[v]) continue;

         split(v, x);

         maior = max(maior, sz[v]);
    }

    if(maior < best.f) best = pii(maior, x);
}

inline int find_centroid(int x)
{
    tot = tam(x, x);

    best = pii(2*Ni, 0);

    split(x, x);

    return best.s;
}

inline int decomp(int x)
{
	x = find_centroid(x);

	block[x] = 1;

	for(auto v: grafo[x])
	{
		if(block[v.f]) continue;

		v.f = decomp(v.f);

		tree[x].push_back(v.f);

		tree[v.f].push_back(x);
	}

	return x;
}

inline void dfs2(int x, int p)
{
	pai[x] = p;

	for(auto v: tree[x])
	{
		if(v == p) continue;

		pai[v] = x;

		dfs2(v, x);
	}
}

inline ll distancia(int a, int b)
{
	return dist[a] + dist[b] - 2*dist[lca(a, b)];
}

inline void paint(int x)
{
	ans[x] = 0;

	last_upd[x] = cnt_upd;

	int u = x;

	while(1)
	{
		if(last_upd[pai[x]] != cnt_upd) ans[pai[x]] = distancia(u, pai[x]);

		else ans[pai[x]] = min(ans[pai[x]], distancia(u, pai[x]));

		last_upd[pai[x]] = cnt_upd;

		if(x == pai[x]) return;

		x = pai[x];
	}
}

inline void clear(int x)
{
	ans[x] = inf;

	int u = x;

	while(1)
	{
		ans[pai[x]] = inf;

		if(x == pai[x]) return;

		x = pai[x];
	}
}

ll query(int x)
{
	int u = x;

	ll resp = inf;

	if(last_upd[x] == cnt_upd) resp = min(resp, ans[x]);

	while(1)
	{
		if(last_upd[x] == cnt_upd) resp = min(resp, distancia(x, u) + ans[x]);

		if(x == pai[x]) return resp;

		x = pai[x];
	}
}

void Init(int N_, int A[], int B[], int D[])
{
	n = N_;

	for(int i = 0; i < Ni; i++) ans[i] = inf;

	for(int i = 0; i < n - 1; i++)
	{
		int a = A[i], b = B[i], c = D[i];

		a++, b++;

		grafo[a].push_back(pii(b, c));

		grafo[b].push_back(pii(a, c));
	}

	init();

	root = decomp(1);

	dfs2(root, root);
}

ll Query(int S, int X[], int T, int Y[])
{
	ll ans = inf;

	++cnt_upd;

	for(int i = 0; i < S ; i++) paint(X[i] + 1);

	for(int i = 0; i < T; i++) ans = min(ans, query(Y[i] + 1));

	//for(int i = 0; i < S; i++) clear(X[i] + 1);

	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void build()':
factories.cpp:26:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < euler.size(); i++) dp[i][0] = pii(deep[i], euler[i]);
                    ^
factories.cpp:30:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < euler.size(); i++)
                        ^
factories.cpp: In function 'void dfs(int, int)':
factories.cpp:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[x].size(); i++)
                   ^
factories.cpp: In function 'void init()':
factories.cpp:80:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < euler.size(); i++) deep[i] = nivel[euler[i]];
                   ^
factories.cpp: In function 'int tam(int, int)':
factories.cpp:94:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < grafo[x].size(); i++)
                      ^
factories.cpp: In function 'void split(int, int)':
factories.cpp:110:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < grafo[x].size(); i++)
                      ^
factories.cpp: In function 'void clear(int)':
factories.cpp:200:6: warning: unused variable 'u' [-Wunused-variable]
  int u = x;
      ^

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