QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#410668#6662. 기지 간소화Unknown1508Compile Error//C++203.5kb2024-05-14 11:13:522024-05-15 12:10:44

Judging History

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

  • [2024-05-15 12:10:44]
  • 管理员手动重测该提交记录
  • [2024-05-14 11:13:52]
  • 提交

answer

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

using ii = pair<int, int>;
const int mod = 1e9 + 7;

namespace {

inline int c2(int x){
	return (1LL * x * (x - 1) / 2) % mod;
}

struct Segtree {
	struct Node {
		int sz;
		ii prefix, suffix;
		int sum;

		Node() {}
		Node(int x): sz(1), prefix(1, x), suffix(1, x), sum(1) {}
		Node(int _sz, ii _prefix, ii _suffix, int _sum):
			sz(_sz), prefix(_prefix), suffix(_suffix), sum(_sum) {}

		Node operator + (const Node &node) const {
			Node res;
			res.sz = sz + node.sz;
			res.sum = (sum + node.sum) % mod;
			if (suffix.second == node.prefix.second){
				res.sum = (res.sum - c2(suffix.first + 1)) % mod;
				res.sum = (res.sum - c2(node.prefix.first + 1)) % mod;
				res.sum = (res.sum + c2(suffix.first + node.prefix.first + 1)) % mod;
			}

			res.prefix = (prefix.first == sz && prefix.second == node.prefix.second)
				? pair{node.prefix.first + sz, node.prefix.second} : prefix;
			res.suffix = (node.suffix.first == node.sz && node.suffix.second == suffix.second)
				? pair{suffix.first + node.sz, suffix.second} : node.suffix;

			return res;
		}
	};

	vector<Node> tree;
	int _n;

	Segtree() {}
	Segtree(int N): tree(4 * N), _n(N) {
		build(1, 0, _n - 1);
	}

	void build(int i, int l, int r){
		if (l == r) tree[i] = Node(0);
		else{
			int mid = (l + r) >> 1;
			build(i<<1, l, mid);
			build(i<<1|1, mid+1, r);
			tree[i] = tree[i<<1] + tree[i<<1|1];
		}
	}

	void update(int pos, int val){
		update(1, 0, _n - 1, pos, val);
	}

	void update(int i, int l, int r, int pos, int val){
		if (l == pos && r == pos) tree[i] = Node(val);
		else{
			int mid = (l + r) >> 1;
			if (pos <= mid) update(i<<1, l, mid, pos, val);
			else update(i<<1|1, mid+1, r, pos, val);
			tree[i] = tree[i<<1] + tree[i<<1|1];
		}
	}

	int get() { return tree[1].sum; }
};

int n;
vector<int> sz;
vector<vector<ii>> adj;

void predfs(int x, int p = -1){
	sz[x] = 1;
	for (auto &edge: adj[x]){
		auto [k, w] = edge;
		if (k == p) continue;
		predfs(k, x);
		sz[x] += sz[k];
		if (adj[x][0].first == p || sz[k] > sz[adj[x][0].first]) swap(adj[x][0], edge);
	}
}

vector<int> tin, tout, order;
int res = 0;
Segtree st;

void dfs_in_out(int x, int p = -1){
	tin[x] = order.size();
	order.push_back(x);

	for (auto [k, w]: adj[x]){
		if (k == p) continue;
		dfs_in_out(k, x);
	}

	tout[x] = order.size() - 1;
}

void dfs(int x, int p = -1){
	for (int i = (int)adj[x].size() - 1; i >= 0; i--){
		auto [k, w] = adj[x][i];
		if (k == p) continue;

		dfs(k, x);

		res = (res + 1LL * w * (c2(n + 1) - st.get())) % mod;

		if (i > 0){
			for (int j = tin[k]; j <= tout[k]; j++){
				st.update(order[j], 0);
			}
		}
	}

	for (int i = 1; i < (int)adj[x].size(); i++){
		auto [k, w] = adj[x][i];
		if (k == p) continue;

		for (int j = tin[k]; j <= tout[k]; j++){
			st.update(order[j], 1);
		}
	}

	st.update(x, 1);
}

}

int maintainance_costs_sum(vector<int> U, vector<int> V, vector<int> W){
	n = U.size() + 1;

	sz.resize(n);
	tin.resize(n);
	tout.resize(n);
	adj.resize(n);

	for (int i = 0; i < n-1; i++){
		adj[U[i]].emplace_back(V[i], W[i]);
		adj[V[i]].emplace_back(U[i], W[i]);
	}

	predfs(0);
	dfs_in_out(0);
	st = Segtree(n);
	dfs(0);

	return res;
}

#ifdef LOCAL

int main(){
	int n; cin >> n;

	vector<int> U(n-1), V(n-1), W(n-1);

	for (int i = 0; i < n-1; i++){
		cin >> U[i] >> V[i] >> W[i];
	}

	cout << maintainance_costs_sum(U, V, W) << "\n";
}

#endif

Details

/usr/bin/ld: /tmp/ccMODlWG.o: in function `main':
implementer.cpp:(.text.startup+0x146): undefined reference to `maintenance_costs_sum(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status