Submission #378475

#	Time	Username	Problem	Language	Result	Execution time	Memory
378475		arwaeystoamneg	공장들 (JOI14_factories)	C++17	15 / 100	8051 ms	133356 KiB

factories

/*
ID: awesome35
LANG: C++14
TASK: vans
*/
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
#define endl '\n'
#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;//1000000007
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}
/**/
#ifndef arwaeystoamneg
#include "factories.h"
#endif
const int SZ = 20;
int n;
vector<vpi>adj;
vi visited, sizes, parent;
struct centroid
{
	void dfs(int i, int p)
	{
		// visit i
		sizes[i] = 1;
		for (auto x : adj[i])
		{
			if (x.f == p || visited[i] == 1)
				continue;
			dfs(x.f, i);
			sizes[i] += sizes[x.f];
		}
	}
	int dfs_centroid(int i, int p, int n)
	{
		// visit i, find the centroid c
		// recurrent if i has a subtree larger than n/2;
		for (auto x : adj[i])
		{
			if (x.f == p)
				continue;
			if (sizes[x.f] > n / 2)
				return dfs_centroid(x.f, i, n);
		}
		return i;
	}
	void build(int i, int p)
	{
		// first dfs to generate size of subtree starting from node i
		// 2nd dfs to find the centroid
		dfs(i, p);
		int centroid = dfs_centroid(i, p, sizes[i]);
		visited[centroid] = 1;
		parent[centroid] = p;
		//cout << centroid << endl;
		// remove the edge from centroid to all its child, build from its child
		for (auto x : adj[centroid])
		{
			if (x.f == parent[centroid])
				continue;
			//cout << "working on subtree of " << x << endl;
			if (visited[x.f])
				continue;
			build(x.f, centroid);
		}
	}
	void init()
	{
		visited.rsz(n);
		sizes.rsz(n);
		parent.rsz(n);
		build(0, -1);
	}
};
template<int SZ>struct lca
{
	vector<vi>jump;
	vi parent, depth;
	vll dist;
	void dfs(int i, int p)
	{
		parent[i] = p;
		trav(x, adj[i])
		{
			if (x.f == p)continue;
			depth[x.f] = depth[i] + 1;
			dist[x.f] = dist[i] + x.s;
			dfs(x.f, i);
		}
	}
	void init()
	{
		parent.rsz(n);
		depth.rsz(n);
		dist.rsz(n);
		dfs(0, -1);
		jump.rsz(n, vi(SZ));
		F0R(i, n)jump[i][0] = parent[i];
		F0R(i, SZ - 1)
		{
			F0R(j, n)jump[j][i + 1] = (jump[j][i] == -1 ? -1 : jump[jump[j][i]][i]);
		}
	}
	int get(int a, int b)
	{
		F0R(j, SZ)
		{
			if (b & (1 << j))
			{
				a = jump[a][j];
			}
		}
		return a;
	}
	int LCA(int a, int b)
	{
		if (depth[a] < depth[b])swap(a, b);
		a = get(a, depth[a] - depth[b]);
		if (a == b)return a;
		int j = SZ;
		while (j)
		{
			j--;
			int ta = jump[a][j], tb = jump[b][j];
			if (ta != tb)a = ta, b = tb;
		}
		return parent[a];
	}
	ll val(int a, int b)
	{
		return dist[a] + dist[b] - 2 * dist[LCA(a, b)];
	}
};
vll dp;
centroid g;
lca<SZ> g1;
void Init(int N, int A[], int B[], int D[]) 
{
	n = N;
	adj.rsz(n);
	F0R(i, n - 1)
	{
		adj[A[i]].pb({ B[i],D[i] });
		adj[B[i]].pb({ A[i],D[i] });
	}
	g.init();
	g1.init();
	dp.rsz(n, linf);
}
long long Query(int S, int X[], int T, int Y[]) 
{
	ll ans = linf;
	vi todo;
	F0R(i, S)
	{
		int x = X[i], t = X[i];
		while (t != -1)
		{
			dp[t] = min(dp[t], g1.val(x, t));
			todo.pb(t);
			t = parent[t];
		}
	}
	F0R(i, T)
	{
		int x = Y[i], t = Y[i];
		while (t != -1)
		{
			ans = min(ans, dp[t] + g1.val(x, t));
			t = parent[t];
		}
	}
	trav(x, todo)dp[x] = linf;
	return ans;
}
#ifdef arwaeystoamneg
int main()
{
	setIO("test1");
	int n, q;
	cin >> n >> q;
	const int MAX = 20;
	int A[MAX], B[MAX], D[MAX], X[MAX], Y[MAX];
	F0R(i, n - 1)cin >> A[i] >> B[i] >> D[i];
	Init(n, A, B, D);
	while (q--)
	{
		int s, t;
		cin >> s >> t;
		F0R(i, s)cin >> X[i];
		F0R(i, t)cin >> Y[i];
		cout << Query(s, X, t, Y) << endl;
	}
}
#endif

Compilation message (stderr)

factories.cpp: In function 'void setIO(std::string)':
factories.cpp:53:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   53 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
factories.cpp:55:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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