oj.uz

답안 #378857

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
378857 2021-03-17T06:19:15 Z arwaeystoamneg 공장들 (JOI14_factories) C++17
100 / 100
 5318 ms 183292 KB 
/*
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

Compilation message

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 12524 KB Output is correct
2 Correct 349 ms 21484 KB Output is correct
3 Correct 384 ms 21356 KB Output is correct
4 Correct 319 ms 21444 KB Output is correct
5 Correct 360 ms 21612 KB Output is correct
6 Correct 261 ms 21340 KB Output is correct
7 Correct 362 ms 21484 KB Output is correct
8 Correct 343 ms 21356 KB Output is correct
9 Correct 395 ms 21740 KB Output is correct
10 Correct 311 ms 21424 KB Output is correct
11 Correct 363 ms 21356 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12268 KB Output is correct
2 Correct 2125 ms 133684 KB Output is correct
3 Correct 3434 ms 136204 KB Output is correct
4 Correct 831 ms 152660 KB Output is correct
5 Correct 4211 ms 183292 KB Output is correct
6 Correct 3281 ms 156052 KB Output is correct
7 Correct 975 ms 58988 KB Output is correct
8 Correct 452 ms 59524 KB Output is correct
9 Correct 1099 ms 63216 KB Output is correct
10 Correct 972 ms 60320 KB Output is correct

Subtask #3
67.0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 12524 KB Output is correct
2 Correct 349 ms 21484 KB Output is correct
3 Correct 384 ms 21356 KB Output is correct
4 Correct 319 ms 21444 KB Output is correct
5 Correct 360 ms 21612 KB Output is correct
6 Correct 261 ms 21340 KB Output is correct
7 Correct 362 ms 21484 KB Output is correct
8 Correct 343 ms 21356 KB Output is correct
9 Correct 395 ms 21740 KB Output is correct
10 Correct 311 ms 21424 KB Output is correct
11 Correct 363 ms 21356 KB Output is correct
12 Correct 9 ms 12268 KB Output is correct
13 Correct 2125 ms 133684 KB Output is correct
14 Correct 3434 ms 136204 KB Output is correct
15 Correct 831 ms 152660 KB Output is correct
16 Correct 4211 ms 183292 KB Output is correct
17 Correct 3281 ms 156052 KB Output is correct
18 Correct 975 ms 58988 KB Output is correct
19 Correct 452 ms 59524 KB Output is correct
20 Correct 1099 ms 63216 KB Output is correct
21 Correct 972 ms 60320 KB Output is correct
22 Correct 2566 ms 142972 KB Output is correct
23 Correct 2578 ms 145276 KB Output is correct
24 Correct 3928 ms 145564 KB Output is correct
25 Correct 4100 ms 142356 KB Output is correct
26 Correct 4128 ms 138772 KB Output is correct
27 Correct 5318 ms 162024 KB Output is correct
28 Correct 1018 ms 138964 KB Output is correct
29 Correct 4171 ms 138508 KB Output is correct
30 Correct 4214 ms 137680 KB Output is correct
31 Correct 4288 ms 138368 KB Output is correct
32 Correct 1161 ms 64108 KB Output is correct
33 Correct 461 ms 60052 KB Output is correct
34 Correct 795 ms 56616 KB Output is correct
35 Correct 847 ms 56720 KB Output is correct
36 Correct 1087 ms 57324 KB Output is correct
37 Correct 1068 ms 57452 KB Output is correct