oj.uz

답안 #379675

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
379675 2021-03-19T02:35:07 Z mode149256 공장들 (JOI14_factories) C++17
15 / 100
 8000 ms 253708 KB 
/*input

*/
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

namespace my_template {
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
}
using namespace my_template;

const int MOD = 1000000007;
const ll INF = 1e14;
const int MX = 500101;
const int L = 19;

int n;
vector<vector<pair<int, ll>>> edges;
vi dep;
vii p;
vll w;
vi in;
vi out;
int piv;

void dfs(int x, int par) {
	in[x] = piv++;
	for (auto u : edges[x]) {
		if (u.x == par) continue;

		int b = u.x;
		dep[b] = dep[x] + 1;
		p[b][0] = x;
		w[b][0] = u.y;
		for (int i = 1; i < L; ++i)
		{
			p[b][i] = p[p[b][i - 1]][i - 1];
			w[b][i] = w[b][i - 1] + w[p[b][i - 1]][i - 1];
		}
		dfs(u.x, x);
	}
	out[x] = piv;
}

// a is ancestor of b
int anc(int a, int b) {
	return in[a] < in[b] and out[b] <= out[a];
}

int lca(int a, int b) {
	if (dep[a] > dep[b]) swap(a, b);

	// a
	// b
	for (int i = L - 1; i >= 0; --i)
	{
		if (dep[b] - (1 << i) >= dep[a])
			b = p[b][i];
	}
	assert(dep[a] == dep[b]);
	if (a == b) return a;

	for (int i = L - 1; i >= 0; i--)
	{
		if (p[a][i] != p[b][i]) {
			a = p[a][i];
			b = p[b][i];
		}
	}
	return p[a][0];
}

ll toRoot(int x) {
	ll ret = 0;
	for (int i = L - 1; i >= 0; i--)
	{
		if (p[x][i] != 0) {
			ret += w[x][i];
			x = p[x][i];
		}
	}
	if (x) ret += w[x][0];

	return ret;
}

ll dis(int a, int b) {
	int l = lca(a, b);
	return toRoot(a) + toRoot(b) - 2 * toRoot(l);
}

void make_lca() {
	dep = vi(n);
	p = vii(n, vi(L, 0));
	w = vll(n, vl(L, 0));
	in = vi(n);
	out = vi(n);

	dep[0] = 0;
	p[0][0] = 0;
	w[0][0] = 0;
	piv = 0;

	dfs(0, -1);
}
vi kas;

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	edges.resize(N);
	kas = vi(N, -1);
	for (int i = 0; i < N - 1; ++i)
	{
		int a = A[i];
		int b = B[i];
		int d = D[i];
		edges[a].emplace_back(b, d);
		edges[b].emplace_back(a, d);
	}

	make_lca();
}

ll Query(int S, int X[], int T, int Y[]) {
	vi visi;
	for (int i = 0; i < S; ++i) {
		visi.emplace_back(X[i]);
		kas[X[i]] = 1;
	}
	for (int i = 0; i < T; ++i) {
		visi.emplace_back(Y[i]);
		kas[Y[i]] = 2;
	}

	sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
		return in[a] < in[b];
	});

	for (int i = 1; i < S + T; ++i)
	{
		int l = lca(visi[i - 1], visi[i]);
		visi.emplace_back(l);
		if (kas[l] == -1)
			kas[l] = 0;
	}

	sort(visi.begin(), visi.end(), [&](const int & a, const int & b) {
		return in[a] < in[b];
	});

	visi.erase(unique(visi.begin(), visi.end()), visi.end());

	// print(visi);
	ll ats = INF;
	unordered_map<int, vl> low;
	vector<int> ver;

	ver.emplace_back(visi[0]);
	low[visi[0]] = vl{INF, INF};
	if (kas[visi[0]]) low[visi[0]][kas[visi[0]] - 1] = 0;

	for (int i = 1; i < (int)visi.size(); ++i)
	{
		while (!anc(ver.back(), visi[i])) {
			int a = ver.back(); ver.pop_back();
			int b = ver.back();

			ll d = dis(a, b);
			if (kas[a] + kas[b] == 3)
				ats = min(ats, d);

			//   b
			//  /  c
			// a

			low[b][0] = min(low[b][0], low[a][0] + d);
			low[b][1] = min(low[b][1], low[a][1] + d);
		}
		ver.emplace_back(visi[i]);
		low[visi[i]] = vl{INF, INF};
		if (kas[visi[i]]) low[visi[i]][kas[visi[i]] - 1] = 0;
	}

	while (ver.size() >= 2) {
		int a = ver.back(); ver.pop_back();
		int b = ver.back();
		ll d = dis(a, b);
		// printf("a = %d, b = %d, d = %lld\n", a, b, d);
		if (kas[a] + kas[b] == 3)
			ats = min(ats, d);

		//   b
		//  /  c
		// a

		low[b][0] = min(low[b][0], low[a][0] + d);
		low[b][1] = min(low[b][1], low[a][1] + d);
	}

	for (auto u : visi) {
		// printf("u = %d, low = %lld %lld\n", u, low[u][0], low[u][1]);
		ats = min(ats, low[u][0] + low[u][1]);
		kas[u] = -1;
	}
	return ats;
}

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 1004 KB Output is correct
2 Correct 2134 ms 20256 KB Output is correct
3 Correct 2863 ms 20112 KB Output is correct
4 Correct 2603 ms 20404 KB Output is correct
5 Correct 2182 ms 20432 KB Output is correct
6 Correct 1665 ms 20204 KB Output is correct
7 Correct 2799 ms 19984 KB Output is correct
8 Correct 2567 ms 20340 KB Output is correct
9 Correct 2222 ms 20552 KB Output is correct
10 Correct 1580 ms 20088 KB Output is correct
11 Correct 2848 ms 20228 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 620 KB Output is correct
2 Correct 3583 ms 225940 KB Output is correct
3 Correct 7443 ms 228160 KB Output is correct
4 Correct 2329 ms 223040 KB Output is correct
5 Correct 6907 ms 253708 KB Output is correct
6 Correct 7882 ms 230504 KB Output is correct
7 Execution timed out 8100 ms 64060 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 1004 KB Output is correct
2 Correct 2134 ms 20256 KB Output is correct
3 Correct 2863 ms 20112 KB Output is correct
4 Correct 2603 ms 20404 KB Output is correct
5 Correct 2182 ms 20432 KB Output is correct
6 Correct 1665 ms 20204 KB Output is correct
7 Correct 2799 ms 19984 KB Output is correct
8 Correct 2567 ms 20340 KB Output is correct
9 Correct 2222 ms 20552 KB Output is correct
10 Correct 1580 ms 20088 KB Output is correct
11 Correct 2848 ms 20228 KB Output is correct
12 Correct 6 ms 620 KB Output is correct
13 Correct 3583 ms 225940 KB Output is correct
14 Correct 7443 ms 228160 KB Output is correct
15 Correct 2329 ms 223040 KB Output is correct
16 Correct 6907 ms 253708 KB Output is correct
17 Correct 7882 ms 230504 KB Output is correct
18 Execution timed out 8100 ms 64060 KB Time limit exceeded
19 Halted 0 ms 0 KB -