제출 #378857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378857		arwaeystoamneg	공장들 (JOI14_factories)	C++17	100 / 100	5318 ms	183292 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;
const int MAX = 5e5 + 5;
int n;
vpi adj[MAX];
int visited[MAX], sizes[MAX], parent[MAX];
ll dist[MAX][SZ];
int temp[MAX];
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 get_dist(int i, int p, ll d)
	{
		dist[i][temp[i]++] = d;
		trav(x, adj[i])
		{
			if (x.f == p || visited[x.f])continue;
			get_dist(x.f, i, d + x.s);
		}
	}
	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]);
		get_dist(centroid, -1, 0);
		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()
	{
		F0R(i, n)visited[i] = 0, sizes[i] = 0, parent[i] = 0;
		build(0, -1);
	}
};
ll dp[MAX];
centroid g;
//lca<SZ> g1;
//ll dist[MAX][SZ];
void Init(int N, int A[], int B[], int D[]) 
{
	n = N;
	F0R(i, n - 1)
	{
		adj[A[i]].pb({ B[i],D[i] });
		adj[B[i]].pb({ A[i],D[i] });
	}
	F0R(i, n)temp[i] = 0;
	g.init();
	//g1.init();
	F0R(i, n)dp[i] = linf;
}
long long Query(int S, int X[], int T, int Y[]) 
{
	ll ans = linf;
	if (S > T)
		swap(S, T), swap(X, Y);
	F0R(i, S)
	{
		int x = X[i], t = X[i];
		int j = temp[x] - 1;
		while (t != -1)
		{
			dp[t] = min(dp[t], dist[x][j--]);
			t = parent[t];
		}
	}
	F0R(i, T)
	{
		int x = Y[i], t = Y[i];
		int j = temp[x] - 1;
		while (t != -1)
		{
			ans = min(ans, dp[t] + dist[x][j--]);
			t = parent[t];
		}
	}
	F0R(i, S)
	{
		int x = X[i], t = X[i];
		while (t != -1)
		{
			dp[t] = linf;
			t = parent[t];
		}
	}
	return ans;
}
#ifdef arwaeystoamneg
int main()
{
	setIO("test1");
	int n, q;
	cin >> n >> q;
	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

컴파일 시 표준 에러 (stderr) 메시지

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:176:7: warning: unused variable 'x' [-Wunused-variable]
  176 |   int x = X[i], t = X[i];
      |       ^
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: 18 / 18
• Subtask 3: 67 / 67