萌新 TLE on #9 求卡常
查看原帖
萌新 TLE on #9 求卡常
560516
喵仔牛奶楼主2023/3/25 18:50

测评记录:https://codeforces.com/problemset/status?my=on

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
namespace FastIO {
	char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() \
	(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++)
	inline int read() {
	    register int sr = 0;
	    register char ch = getchar(), last;
	    while (ch < '0' || ch > '9') last = ch, ch = getchar();
	    while (ch >= '0' && ch <= '9') sr = (sr << 1) + (sr << 3) + (ch ^ 48), ch = getchar();
	    return last == '-' ? -sr : sr;
	}
}
namespace Milkcat {
	using namespace FastIO;
	typedef long long LL;
	const int N = 1e6 + 5, inf = INT_MAX;
	struct edge {
		int u, v, w;
		bool operator < (const edge& x) const {
			return w < x.w;
		}
	} e[N], qwq[N];
	int n, m, k, f[N], a[N];
	vector<edge> t;
	LL ans;
	int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
	void merge(int u, int v) {
		int fu = find(u), fv = find(v);
		if (fu != fv) f[fv] = fu;
	}
	struct ODT {
		struct node {
		    int l, r;
		    mutable int v;
		    node(int L, int R = -1, int V = 0): l(L), r(R), v(V) {}
		    bool operator < (const node& o) const { return l < o.l; }
		    int size() const { return r - l + 1; }
		};
		typedef set<node>::iterator IT;
		set<node> s;
		IT split(int pos) {
			IT it = s.lower_bound(node(pos));
			if (it != s.end() && it->l == pos) return it;
			int L = (-- it)->l, R = it->r, V = it->v;
			s.erase(it), s.insert(node(L, pos - 1, V));
			return s.insert(node(pos, R, V)).first;
		}
		void assign(int l, int r, int val = 0) {
		    IT itr = split(r + 1), itl = split(l);
		    s.erase(itl, itr);
		    s.insert(node(l, r, val));
		}
	} odt;
	struct TreeDecom {
		struct edge {
			int next, to;
			int w;
		} e[N << 1];
		int tot, cnt, a[N], head[N], depth[N], fa[N], siz[N], son[N], top[N], id[N];
		void Add(int u, int v, int w) {
			e[++ cnt].to = v;
			e[cnt].w = w;
			e[cnt].next = head[u];
			head[u] = cnt;
		}
		void add(int u, int v, int w) {
			Add(u, v, w), Add(v, u, w);
		}
		void dfs1(int u, int fat) {
			fa[u] = fat, siz[u] = 1, depth[u] = depth[fa[u]] + 1;
			for (int i = head[u]; i; i = e[i].next) {
				int v = e[i].to;
				if (v == fa[u]) continue;
				dfs1(v, u), a[v] = e[i].w, siz[u] += siz[v];
				if (!son[u] || siz[v] > siz[son[u]])
					son[u] = v;
			}
		}
		void dfs2(int u, int topf) {
			top[u] = topf, id[u] = ++ tot;
			odt.assign(id[u], id[u], a[u]);
			if (son[u]) dfs2(son[u], topf);
			for (int i = head[u]; i; i = e[i].next) {
				int v = e[i].to;
				if (v == fa[u] || v == son[u]) continue;
				dfs2(v, v);
			}
		}
		void updRange(int u, int v, int k) {
			while (top[u] != top[v]) {
				if (depth[top[u]] < depth[top[v]]) swap(u, v);
				odt.assign(id[top[u]], id[u], k), u = fa[top[u]];
			}
			if (depth[u] > depth[v]) swap(u, v);
			if (id[u] < id[v]) odt.assign(id[u] + 1, id[v], k);
		}
	} T;
	int main() {
		n = read(), k = read(), m = read(), odt.s.insert(ODT::node(1, n, 0));
		for (int i = 1; i <= n; i ++) f[i] = i;
		for (int i = 1; i <= k; i ++) {
			qwq[i].u = read(), qwq[i].v = read();
			merge(qwq[i].u, qwq[i].v), T.add(qwq[i].u, qwq[i].v, inf);
		}
		for (int i = 1; i <= m; i ++) e[i].u = read(), e[i].v = read(), e[i].w = read();
		sort(e + 1, e + 1 + m);
		for (int i = 1; i <= m; i ++) {
			int fu = find(e[i].u), fv = find(e[i].v);
			if (fu != fv) merge(e[i].u, e[i].v), T.add(e[i].u, e[i].v, 0);
			else t.push_back(e[i]);
		}
		T.dfs1(1, 0), T.dfs2(1, 1);
		reverse(t.begin(), t.end());
		for (edge pwp : t) T.updRange(pwp.u, pwp.v, pwp.w);
		for (int i = 1; i <= k; i ++) {
			if (T.depth[qwq[i].u] < T.depth[qwq[i].v]) swap(qwq[i].u, qwq[i].v);
			int res = odt.split(T.id[qwq[i].u])->v;
			if (res >= inf) puts("-1"), exit(0);
			ans += res;
		}
		printf("%lld\n", ans);
		return 0;
	}
}
int main() {
	return Milkcat::main();
}

2023/3/25 18:50
加载中...