Submission #921243

#	Time	Username	Problem	Language	Result	Execution time	Memory
921243		BBart888	Factories (JOI14_factories)	C++14	15 / 100	401 ms	159668 KiB

factories

#include <cstdio>
#include <iostream>
#include <vector>
#include <list>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <queue>
#include <stack>
#include <cassert>
#include <cstring>
#include <climits>
#include <functional>
#include <cstdlib>
#include <complex>
#include <array>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <random>
#define fileIO(name) if(fopen(name".in", "r")) {freopen(name".in", "r", stdin); freopen(name".out", "w", stdout);}



using namespace std;
const int MAXN = 2e5 + 111;
using ll = long long;
const int P = 31;
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
using ld = long double;
const ld EPS = 1e-5;
using pii = pair<int, int>;
typedef complex<ll> Point;

int sz[MAXN];
int par[MAXN];
ll best[MAXN];
ll dis[MAXN][25];
vector<pair<int,ll>> adj[MAXN];
bool vis[MAXN];
int lev[MAXN];

int find_size(int v, int p)
{
	if (vis[v])
		return 0;
	sz[v] = 1;
	for (auto u : adj[v])
	{
		if (u.first == p)
			continue;
		sz[v] += find_size(u.first, v);
	}
	return sz[v];
}

int find_centroid(int v, int p, int n)
{
	for (auto u : adj[v])
	{
		if (u.first == p || vis[u.first])
			continue;
		if (sz[u.first] > n / 2)
			return find_centroid(u.first, v, n);
	}
	return v;
}

void calc_it(int v, int p,int C)
{
	for (auto u : adj[v])
	{
		if (u.first == p || vis[u.first])
			continue;
		dis[u.first][lev[u.first] - lev[C]] = dis[v][lev[v] - lev[C]] + u.second;
		calc_it(u.first, v, C);
	}
}

void decompose2(int v, int p)
{
	find_size(v, v);
	
	int c = find_centroid(v, v, sz[v]);

	vis[c] = true;
	calc_it(c, p, c);
	
	for (auto u : adj[c])
	{
		if (u.first == p || vis[u.first])
			continue;
		decompose2(u.first, c);
	}
}


void decompose1(int v, int p)
{
	find_size(v, v);

	int c = find_centroid(v, v, sz[v]);

	vis[c] = true;
	par[c] = p;

	if (p != -1)
		lev[c] = lev[p] + 1;

	for (auto u : adj[c])
	{
		if (u.first == p || vis[u.first])
			continue;
		decompose1(u.first, c);
	}
}


void Init(int n, int a[], int b[], int d[])
{
	for (int i = 0; i < n - 1; i++)
	{
		adj[a[i] + 1].push_back(make_pair(b[i] + 1, d[i]));
		adj[b[i] + 1].push_back(make_pair(a[i] + 1, d[i]));
	}

	fill(best, best + MAXN, 1e18);
	decompose1(1, -1);
	fill(vis, vis + MAXN, false);
	decompose2(1, -1);
}



ll Query(int s, int x[], int t, int y[])
{
	ll ans = 1e18;
	for (int i = 0; i < s; i++)
		x[i]++;
	for (int i = 0; i < t; i++)
		y[i]++;

	for (int i = 0; i < s; i++)
	{
		int a = x[i];
		int j = 0;
		while (a != -1)
		{
			best[a] = min(best[a], dis[x[i]][j]);
			j++;
			a = par[a];
		}
	}

	for (int i = 0; i < t; i++)
	{
		int b = y[i];
		int j = 0;
		while (b != -1)
		{
			ans = min(ans, best[b] + dis[y[i]][j]);
			j++;
			b = par[b];
		}
	}

	for (int i = 0; i < s; i++)
	{
		int a = x[i];
		while (a != -1)
		{
			best[a] = 1e18;
			a = par[a];
		}
	}

	return ans;
}

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