제출 #920670

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920670		BBart888	공장들 (JOI14_factories)	C++14	0 / 100	9 ms	35672 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);}
#include "factories.h"



using namespace std;
const int MAXN = 4e5 + 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 n;
vector<pair<int,int>> adj[MAXN];
int sz[MAXN];
bool vis[MAXN];
ll best[MAXN];
ll dis[MAXN][20];
int lev[MAXN];
int par[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 dfs(int v,int S, int p)
{
	for (auto u : adj[v])
	{
		if (u.first == p || vis[u.first])
			continue;
		dis[u.first][lev[u.first] - lev[S]] = 
			dis[v][lev[v] - lev[S]] + u.second;
		dfs(u.first, S, v);
	}
}


void decomp1(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 (!vis[u.first])
			decomp1(u.first, c);
	}
}


void decomp2(int v)
{
	find_size(v, v);

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

	vis[c] = true;
	dfs(c, -1, c);
	for (auto u : adj[c])
	{
		if (!vis[u.first])
			decomp2(u.first);
	}
}




void Init(int _n, int a[], int b[], int d[])
{
	fill(par, par + MAXN, -1);
	fill(best, best + MAXN, 1e18);
	for (int i = 0; i < n-1; i++)
	{
		adj[a[i] + 1].push_back({ b[i] + 1,d[i] });
		adj[b[i] + 1].push_back({ a[i] + 1,d[i] });
	}
	decomp1(1, -1);
	fill(vis, vis + MAXN, 0);
	decomp2(1);
}



ll Query(int s, int x[], int t, int y[])
{
	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];
		}
	}
	ll ans = 1e18;
	for (int i = 0; i < t; i++)
	{
		int b = y[i];
		int j = 0;
		while (b != -1)
		{
			ans = min(ans, dis[y[i]][j] + best[b]);
			b = par[b];
			j++;
		}
	}

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

	return ans;
}

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