oj.uz

Submission #643010

# Submission time Handle Problem Language Result Execution time Memory
643010 2022-09-21T04:12:15 Z ymm Factories (JOI14_factories) C++17
100 / 100
 2803 ms 188676 KB 
#include "factories.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 510'010;
const int lg = 19;
vector<pll> A0[N];
vector<int> ord;
int rmq[lg+1][2*N];
int st[N], ft[N], h[N];
ll dis[N];
int n;

void dfs(int v, int p, ll d, int h)
{
	::h[v] = h;
	st[v] = ord.size();
	ord.push_back(v);
	dis[v] = d;
	for (auto [u, w] : A0[v]) {
		if (u != p) {
			dfs(u, v, d + w, h+1);
			ord.push_back(v);
		}
	}
	ft[v] = ord.size();
}

#define HMIN(x, y) (h[x]<h[y]?(x):(y))

void rmq_init()
{
	int n = ord.size();
	Loop (i,0,n)
		rmq[0][i] = ord[i];
	{ vector<int> dard; ord.swap(dard); }
	Loop (i,0,lg)
		for (int j = 0; j + (2<<i) <= n; ++j)
			rmq[i+1][j] = HMIN(rmq[i][j], rmq[i][j+(1<<i)]);
}

pair<ll,int> get_dis(int x, int y)
{
	ll ans = dis[x] + dis[y];
	if (st[x] > st[y]) {
		int tmp = x;
		x = y;
		y = tmp;
	}
	x = st[x];
	y = st[y]+1;
	int l = __lg(y - x);
	int a = HMIN(rmq[l][x], rmq[l][y - (1<<l)]);
	ans -= 2*dis[a];
	return {ans, a};
}

void Init(int N, int X[], int Y[], int D[])
{
	n = N;
	Loop (i,0,n) {
		A0[X[i]].push_back({Y[i],D[i]});
		A0[Y[i]].push_back({X[i],D[i]});
	}
	dfs(0, 0, 0, 0);
	rmq_init();
	Loop (i,0,N) {
		vector<pll> dard;
		A0[i].swap(dard);
	}
}

ll dij(const vector<vector<pll>> &A, const vector<int> &x, const vector<int> &y)
{
	static ll dis[N];
	fill(dis, dis+A.size(), (ll)1e18);
	priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> q;
	for (int v : x) {
		dis[v] = 0;
		q.push({0,v});
	}
	while (q.size()) {
		auto [d, v] = q.top();
		q.pop();
		if (d != dis[v])
			continue;
		for (auto [u, w] : A[v]) {
			if (d + w < dis[u]) {
				dis[u] = d + w;
				q.push({dis[u], u});
			}
		}
	}
	ll ans = 1e18;
	for (int v : y)
		ans = min(ans, dis[v]);
	return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
	static bool imp_vis[N];
	vector<int> imp;
	Loop (i,0,S) {
		imp_vis[X[i]] = 1;
		imp.push_back(X[i]);
	}
	Loop (i,0,T) {
		imp_vis[Y[i]] = 1;
		imp.push_back(Y[i]);
	}
	if (!imp_vis[0]) {
		imp_vis[0] = 1;
		imp.push_back(0);
	}
	sort(imp.begin(), imp.end(), [](int v, int u){return st[v] < st[u];});
	int kooft_ = imp.size();
	Loop (i,1,kooft_) {
		int v = get_dis(imp[i], imp[i-1]).second;
		if (!imp_vis[v]) {
			imp_vis[v] = 1;
			imp.push_back(v);
		}
	}
	sort(imp.begin(), imp.end(), [](int v, int u){return st[v] < st[u];});
	vector<int> stk = {0};
	vector<vector<pll>> A(imp.size());
	Loop (i,1,imp.size()) {
		int v = imp[i];
		while (ft[imp[stk.back()]] <= st[v])
			stk.pop_back();
		ll d = get_dis(imp[stk.back()], v).first;
		A[stk.back()].push_back({i, d});
		A[i].push_back({stk.back(), d});
		stk.push_back(i);
	}
	for (auto v : imp)
		imp_vis[v] = 0;
	vector<int> x, y;
	static int dard1[N];
	Loop (i,0,imp.size())
		dard1[imp[i]] = i;
	Loop (i,0,S)
		x.push_back(dard1[X[i]]);
	Loop (i,0,T)
		y.push_back(dard1[Y[i]]);
	return dij(A, x, y);
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
factories.cpp:133:2: note: in expansion of macro 'Loop'
  133 |  Loop (i,1,imp.size()) {
      |  ^~~~
factories.cpp:3:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    3 | #define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
      |                                        ^
factories.cpp:146:2: note: in expansion of macro 'Loop'
  146 |  Loop (i,0,imp.size())
      |  ^~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12756 KB Output is correct
2 Correct 962 ms 21516 KB Output is correct
3 Correct 1108 ms 21416 KB Output is correct
4 Correct 943 ms 21816 KB Output is correct
5 Correct 746 ms 21904 KB Output is correct
6 Correct 720 ms 21464 KB Output is correct
7 Correct 1079 ms 21452 KB Output is correct
8 Correct 995 ms 21680 KB Output is correct
9 Correct 741 ms 21808 KB Output is correct
10 Correct 719 ms 21504 KB Output is correct
11 Correct 1076 ms 21560 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12500 KB Output is correct
2 Correct 1386 ms 137508 KB Output is correct
3 Correct 1492 ms 140364 KB Output is correct
4 Correct 909 ms 130856 KB Output is correct
5 Correct 1144 ms 165096 KB Output is correct
6 Correct 1593 ms 141812 KB Output is correct
7 Correct 1495 ms 44560 KB Output is correct
8 Correct 728 ms 42712 KB Output is correct
9 Correct 769 ms 48416 KB Output is correct
10 Correct 1462 ms 45680 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 12756 KB Output is correct
2 Correct 962 ms 21516 KB Output is correct
3 Correct 1108 ms 21416 KB Output is correct
4 Correct 943 ms 21816 KB Output is correct
5 Correct 746 ms 21904 KB Output is correct
6 Correct 720 ms 21464 KB Output is correct
7 Correct 1079 ms 21452 KB Output is correct
8 Correct 995 ms 21680 KB Output is correct
9 Correct 741 ms 21808 KB Output is correct
10 Correct 719 ms 21504 KB Output is correct
11 Correct 1076 ms 21560 KB Output is correct
12 Correct 9 ms 12500 KB Output is correct
13 Correct 1386 ms 137508 KB Output is correct
14 Correct 1492 ms 140364 KB Output is correct
15 Correct 909 ms 130856 KB Output is correct
16 Correct 1144 ms 165096 KB Output is correct
17 Correct 1593 ms 141812 KB Output is correct
18 Correct 1495 ms 44560 KB Output is correct
19 Correct 728 ms 42712 KB Output is correct
20 Correct 769 ms 48416 KB Output is correct
21 Correct 1462 ms 45680 KB Output is correct
22 Correct 2732 ms 139824 KB Output is correct
23 Correct 2423 ms 166784 KB Output is correct
24 Correct 2803 ms 167608 KB Output is correct
25 Correct 2730 ms 171692 KB Output is correct
26 Correct 2734 ms 166684 KB Output is correct
27 Correct 1993 ms 188676 KB Output is correct
28 Correct 1707 ms 159184 KB Output is correct
29 Correct 2663 ms 166456 KB Output is correct
30 Correct 2670 ms 165912 KB Output is correct
31 Correct 2673 ms 166352 KB Output is correct
32 Correct 1063 ms 65540 KB Output is correct
33 Correct 1031 ms 63532 KB Output is correct
34 Correct 1467 ms 55912 KB Output is correct
35 Correct 1471 ms 55920 KB Output is correct
36 Correct 1644 ms 56652 KB Output is correct
37 Correct 1607 ms 56744 KB Output is correct