QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#159740#7103. Red Black Treeucup-team296#AC ✓1359ms51292kbC++149.4kb2023-09-02 18:30:092023-09-02 18:30:09

Judging History

你现在查看的是最新测评结果

  • [2023-09-02 18:30:09]
  • 评测
  • 测评结果:AC
  • 用时:1359ms
  • 内存:51292kb
  • [2023-09-02 18:30:09]
  • 提交

answer

#include <bits/stdc++.h>

/**
 * Author: Niyaz Nigmatullin
 *
 */

using namespace std;

struct edge {
	int from;
	int to;
	int w;
};

string to_string(string s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// usage:
//   auto fun = [&](int i, int j) { return min(i, j); };
//   SparseTable<int, decltype(fun)> st(a, fun);
// or:
//   SparseTable<int> st(a, [&](int i, int j) { return min(i, j); });
template <typename T, class F = function<T(const T&, const T&)>>
class SparseTable {
 public:
  int n;
  vector<vector<T>> mat;
  F func;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    int lg = 32 - __builtin_clz(to - from + 1) - 1;
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

string to_string(edge const &a) {
	return "edge{from=" + to_string(a.from) + ", to=" + to_string(a.to) + ", w=" + to_string(a.w) + "}";
}

vector<long long> solveSmart(int n, vector<int> reds, vector<vector<edge>> edges, vector<vector<int>> queries) {
	vector<int> is_red(n);
	for (int &x: reds) {
		is_red[x] = 1;
	}
	vector<int> component_id(n, -1);
	int K = 1;
	while (1 << K < n) K++;
	vector<vector<int>> pp(n, vector<int>(K));
	vector<int> en(n), ex(n);
	vector<long long> depth(n);
	int T = 0;
	vector<int> global_parent(n);
	function<void(int, int)> global_dfs = [&global_parent, &edges, &global_dfs](int v, int p) {
		global_parent[v] = p;
		for (auto &e: edges[v]) {
			if (e.to != p) 
				global_dfs(e.to, v);
		}
	};
	global_dfs(0, -1);
	function<void(int, int, int, long long)> dfs = [&](int v, int p, int c, long long d) {
		component_id[v] = c;
		depth[v] = d;
		en[v] = T++;
		// debug(n, v);
		pp[v][0] = (p < 0 ? v : p);
		for (int i = 1; i < K; i++) {
			pp[v][i] = pp[pp[v][i - 1]][i - 1];
		}
		for (auto &e : edges[v]) {
			if (component_id[e.to] < 0 && !is_red[e.to] && e.to != global_parent[v]) {
				dfs(e.to, v, c, d + e.w);
			}
		}
		ex[v] = T;
	};
	int components = 0;
	for (int start : reds) {
		T = 0;
		dfs(start, -1, components++, 0);
	}
	auto anc = [&en, &ex](int v, int u) {
		return en[v] <= en[u] && ex[u] <= ex[v];
	};
	auto lca = [&anc, &pp, &K](int v, int u) {
		if (anc(v, u)) return v;
		for (int i = K - 1; i >= 0; i--) {
			if (!anc(pp[v][i], u)) {
				v = pp[v][i];
			}
		}
		return pp[v][0];
	};
	// debug(n);
	// debug(component_id);
	// debug(depth);
	// debug(en);
	// debug(ex);
	auto solve_for_component = [&](vector<int> vs) {
		vector<int> only = vs;
		vector<long long> dOnly(only.size());
		for (int i = 0; i < (int) only.size(); i++) {
			dOnly[i] = depth[only[i]];
		}
		SparseTable<long long, function<long long(long long, long long)>> table(dOnly, [](long long x, long long y) { return max(x, y); });
		// debug(only, dOnly);
		long long nop = table.get(0, (int) only.size() - 1);
		{
			int cnt = (int) vs.size();
			for (int i = 0; i + 1 < cnt; i++) {
				vs.push_back(lca(vs[i], vs[i + 1]));
			}
		}
		long long best = nop;
		for (int v : vs) {
			int from = (int) (lower_bound(only.begin(), only.end(), v, [&en](int v, int u) {
				return en[v] < en[u];
			}) - only.begin());
			int to;
			{
				int left = -1;
				int right = (int) only.size();
				while (left < right - 1) {
					int mid = (left + right) >> 1;
					if (en[only[mid]] >= ex[v]) {
						right = mid;
					} else {
						left = mid;
					}
				}
				to = right;
			}
			// debug(en);			
			// debug(component_id);
			long long res = table.get(from, to - 1) - depth[v];
			// debug(table.get(from, to - 1));
			// debug(table.get(from, to - 1) - depth[v]);
			if (from > 0) {
				res = max(res, table.get(0, from - 1));
			}
			if (to < (int) only.size()) {
				res = max(res, table.get(to, (int) only.size() - 1));
			}
			// debug(v, from, to, only, res);
			best = min(best, res);
		}
		return pair<long long, long long>(nop, best);
	};
	int q = (int) queries.size();
	vector<long long> result(q);
	for (int cq = 0; cq < q; cq++) {
		vector<int> vs = queries[cq];
		sort(vs.begin(), vs.end(), [&component_id, &en](int v, int u) {
			if (component_id[v] != component_id[u]) {
				return component_id[v] < component_id[u];
			}
			return en[v] < en[u];
		});
		vector<pair<long long, long long>> results;
		for (int from = 0; from < (int) vs.size(); ) {
			int to = from + 1;
			while (to < (int) vs.size() && component_id[vs[to]] == component_id[vs[from]]) {
				to++;
			}
			results.push_back(solve_for_component(vector<int>(vs.begin() + from, vs.begin() + to)));
			from = to;
		}
		vector<long long> suffixMax(results.size());
		for (int i = (int) results.size() - 1; i >= 0; i--) {
			suffixMax[i] = results[i].first;
			if (i + 1 < (int) results.size()) {
				suffixMax[i] = max(suffixMax[i + 1], suffixMax[i]);
			}
		}
		long long current_max = 0;
		long long ans = 1LL << 60;
		for (int i = 0; i < (int) results.size(); i++) {
			long long cur = current_max;
			if (i + 1 < (int) results.size()) cur = max(cur, suffixMax[i + 1]);
			cur = max(cur, min(results[i].first, results[i].second));
			ans = min(ans, cur);
			current_max = max(current_max, results[i].first);
		}
		result[cq] = ans;
	}
	return result;
}

vector<long long> solveStupid(int n, vector<int> reds, vector<vector<edge>> edges, vector<vector<int>> queries) {
	vector<int> is_red(n);
	for (int i : reds) is_red[i] = true;
	int q = (int) queries.size();
	vector<long long> ans(q);
	// debug(edges);
	auto get_ans = [&](vector<int> const &vs) {
		vector<long long> depth(n);
		function<void(int, int, long long)> dfs = [&](int v, int p, long long d) {
			// debug(v, p, d);
			// debug(edges);
			if (is_red[v]) d = 0;
			depth[v] = d;
			for (auto &e : edges[v]) {
				if (e.to != p) {
					dfs(e.to, v, d + e.w);
				}
			}
		};
		dfs(0, -1, 0);
		long long res = 0;
		for (int v : vs) {
			res = max(res, depth[v]);
		}
		return res;
	};
	for (int cq = 0; cq < q; cq++) {
		auto &vs = queries[cq];
		long long cur_ans = get_ans(vs);
		for (int change = 0; change < n; change++) {
			if (is_red[change]) continue;
			is_red[change] = true;
			cur_ans = min(cur_ans, get_ans(vs));
			is_red[change] = false;
		}
		ans[cq] = cur_ans;
	}
	return ans;
}

void solve() {
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> reds(m);
	for (int &x: reds) {
		cin >> x;
		--x;
	}
	vector<vector<edge>> edges(n);
	for (int i = 0; i + 1 < n; i++) {
		int from, to, w;
		cin >> from >> to >> w;
		--from;
		--to;
		edges[from].push_back({from, to, w});
		edges[to].push_back({to, from, w});
	}
	vector<vector<int>> queries(q);
	for (int i = 0; i < q; i++) {
		int cnt;
		cin >> cnt;
		vector<int> vs(cnt);
		for (int &x: vs) {
			cin >> x;
			--x;
		}
		queries[i] = std::move(vs);
	}
	vector<long long> ans = solveSmart(n, reds, edges, queries);
	for (auto &x: ans) {
		cout << x << '\n';
	}
}


mt19937 rng(787788);

void test() {
	for (int it = 0; it < 10000; it++) {
		int n = rng() % 15 + 2;
		vector<int> is_red(n);
		for (int i = 0; i < n; i++) {
			is_red[i] = i == 0 || rng() % 2 == 0;
		}
		vector<int> reds;
		for (int i = 0; i < n; i++) if (is_red[i]) reds.push_back(i);
		vector<vector<edge>> edges(n);
		vector<int> p(n);
		iota(p.begin(), p.end(), 0);
		shuffle(p.begin() + 1, p.end(), rng);
		for (int i = 1; i < n; i++) {
			int to = rng() % i;
			int w = rng() % 1000 + 999999000;
			edges[p[to]].push_back({p[to], p[i], w});
			edges[p[i]].push_back({p[i], p[to], w});
		}
		for (int i = 0; i < n; i++) {
			shuffle(edges[i].begin(), edges[i].end(), rng);
		}
		assert(p[0] == 0);
		int m = rng() % 100 + 1;
		vector<vector<int>> queries(m);
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++) {
				if (rng() % 2 == 0) {
					queries[i].push_back(j);
				}
			}
			if (queries[i].empty()) {
				queries[i].push_back(rng() % n);
			}
		}
		auto ans1 = solveSmart(n, reds, edges, queries);
		auto ans2 = solveStupid(n, reds, edges, queries);
		if (ans1 != ans2) {
			debug(ans1, ans2);
			cout << n << ' ' << reds.size() << ' ' << m << endl;
			for (int i : reds) cout << (i + 1) << ' ';
			cout << '\n';
			for (int i = 0; i < n; i++) {
				for (auto &e: edges[i]) {
					if (i < e.to) {
						cout << i + 1 << ' ' << e.to + 1 << ' ' << e.w << endl;
					}
				}
			}
			for (auto &f: queries) {
				cout << f.size();
				for (auto x : f) cout << " " << x;
				cout << endl;
			}
			assert(ans1 == ans2);
		}
		assert(ans1 == ans2);
	}
}

int main() {
	std::cin.tie(NULL); std::ios::sync_with_stdio(false);

	// test();
	int t;
	cin >> t;
	while (t--) solve();
}

这程序好像有点Bug,我给组数据试试?

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3632kb

input:

2
12 2 4
1 9
1 2 1
2 3 4
3 4 3
3 5 2
2 6 2
6 7 1
6 8 2
2 9 5
9 10 2
9 11 3
1 12 10
3 3 7 8
4 4 5 7 8
4 7 8 10 11
3 4 5 12
3 2 3
1 2
1 2 1
1 3 1
1 1
2 1 2
3 1 2 3

output:

4
5
3
8
0
0
0

result:

ok 7 lines

Test #2:

score: 0
Accepted
time: 1359ms
memory: 51292kb

input:

522
26 1 3
1
1 4 276455
18 6 49344056
18 25 58172365
19 9 12014251
2 1 15079181
17 1 50011746
8 9 2413085
23 24 23767115
22 2 26151339
26 21 50183935
17 14 16892041
9 26 53389093
1 20 62299200
24 18 56114328
11 2 50160143
6 26 14430542
16 7 32574577
3 16 59227555
3 15 8795685
4 12 5801074
5 20 57457...

output:

148616264
148616264
0
319801028
319801028
255904892
317070839
1265145897
1265145897
1072765445
667742619
455103436
285643094
285643094
285643094
317919339
0
785245841
691421476
605409472
479058444
371688030
303203698
493383271
919185207
910180170
919185207
121535083
181713164
181713164
181713164
181...

result:

ok 577632 lines

Extra Test:

score: 0
Extra Test Passed