QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#597143#9132. Painting Fencesucup-team2432#WA 0ms3716kbC++204.3kb2024-09-28 17:09:262024-09-28 17:09:28

Judging History

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

  • [2024-09-28 17:09:28]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3716kb
  • [2024-09-28 17:09:26]
  • 提交

answer

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define all(v) v.begin(),v.end()
#define sz(v) ((ll)v.size())
#define V vector
#define vi V<int>
#define vll V<ll>
#define eb emplace_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fi first
#define se second
#define A array
#define pb push_back
#define mset multiset
#define gpumap __gnu_pbds::gp_hash_table
#define ccumap __gnu_pbds::cc_hash_table
#define ui unsigned int
#define ull unsigned ll
#define i128 __int128
#define cerr if (test) cerr
#define freopen if (test) freopen
#define whtest if (test)
using namespace std;

constexpr int test = 0;

namespace jhsy {
	struct BIT {
		int n; vll a;
		BIT(int n):n(n),a(n,0) {}
		int lbt(int x) {
			return 1<<__builtin_ctz(x);
		}
		void upd(int x,ll k) {
			for (int i = x+1; i <= n; i += lbt(i)) {
				a[i-1] += k;
			}
		}
		ll qry(int x) {
			ll k = 0;
			for (int i = x; i > 0; i -= lbt(i)) {
				k += a[i-1];
			}
			return k;
		}
		ll qry(int l,int r) {
			return qry(r)-qry(l);
		}
	};
	template<class Chk>
	ll pp(ll l,ll r,Chk &&chk) {
		if (!chk(l)) {
			return l;
		}
		while (r-l > 1) {
			ll mid = l+((r-l)>>1);
			if (chk(mid)) {
				l = mid;
			}
			else {
				r = mid;
			}
		}
		return l+1;
	}
	struct HLD {
		int n; vi fa, siz,son,dfn,idfn,top; vector<vi> e;
		HLD(int n):n(n),fa(n,-1),siz(n,1),son(n,-1),dfn(n,-1),top(n),e(n) {}
		void add(int u,int v) {e[u].eb(v); e[v].eb(u);}
		void dfs0(int u) {
			for (auto v:e[u]) {
				if (v != fa[u]) {
					fa[v] = u; dfs0(v); siz[u] += siz[v];
					if (son[u] == -1 || siz[v] > siz[son[u]]) {
						son[u] = v;
					}
				}
			}
		}
		void dfs1(int u,int t) {
			dfn[u] = size(idfn); idfn.eb(u); top[u] = t;
			if (son[u] != -1) {dfs1(son[u],t);}
			for (auto v:e[u]) {
				if (dfn[v] == -1) {dfs1(v,v);}
			}
		}
		void init() {for (int i = 0; i < n; i++) {if (dfn[i] == -1) {dfs0(i); dfs1(i,i);}}}
		int LCA(int x,int y) {
			while (top[x] != top[y]) {
				dfn[top[x]] > dfn[top[y]] ? x = fa[top[x]] : y = fa[top[y]];
			}
			return dfn[x] < dfn[y] ? x : y;
		}
		template<class Chk>
		A<int,2> get(int u,Chk chk = {}) {
			if (!chk(u)) {
				return {u,-1};
			}
			while (fa[top[u]] != -1 && chk(fa[top[u]])) {
				u = fa[top[u]];
			}
			int x = idfn[pp(dfn[top[u]],dfn[u]+1,[&](int x) {
				return !chk(idfn[x]);
			})];
			return {fa[x],x};
		}
	};
	void main() {
		int n,m;
		cin >> n >> m;
		V<V<pii>> e(n); HLD g(n);
		for (int i = 0; i < n-1; i++) {
			int u,v,w;
			cin >> u >> v >> w; u--; v--;
			e[u].eb(v,w); e[v].eb(u,w);
			g.add(u,v);
		}
		g.init();
		vll dep(n);
		{
			auto dfs = [&](auto &&self,int u) -> void {
				for (auto [v,w]:e[u]) {
					if (v != g.fa[u]) {
						dep[v] = dep[u]+w;
						self(self,v);
					}
				}
			};
			dfs(dfs,0);
		}
		V<V<pll>> vec(n);
		while (m--) {
			int c,p;
			cin >> c >> p; p--;
			vll s(c+1),l(c+1);
			for (int i = 0; i < c; i++) {
				int x;
				cin >> x;
				s[i+1] = s[i]+x;
			}
			for (int i = 0; i < c; i++) {
				int x;
				cin >> x;
				l[i+1] = l[i]+x;
			}
			for (int i = 1; i <= c; i++) {
				if (dep[p] >= l[i]) {
					auto [_,q] = g.get(p,[&](int x) {
						return dep[p]-dep[x] < l[i];
					});
					vec[q].eb(p,s[i]);
				}
			}
		}
		vll sum(n),f(n); BIT bit(n);
		auto calc = [&](int u,int v) {
			int flg = u == 1 && v == 3;
			ll res = sum[v];
			for (; g.dfn[g.top[v]] > g.dfn[u]; v = g.fa[g.top[v]]) {
				res += bit.qry(g.dfn[g.top[v]],g.dfn[v]);
				res += sum[g.fa[g.top[v]]]-f[g.top[v]];
			}
			res += bit.qry(g.dfn[u],g.dfn[v]);
			return res;
		};
		auto dfs = [&](auto &&self,int u) -> void {
			for (auto [v,w]:e[u]) {
				if (v != g.fa[u]) {
					self(self,v);
					sum[u] += f[v];
				}
			}
			if (g.son[u] != -1) {
				bit.upd(g.dfn[u],sum[u]-f[g.son[u]]);
			}
			f[u] = sum[u];
			for (auto [v,k]:vec[u]) {
				f[u] = max(f[u],calc(u,v)+k);
			}
		};
		dfs(dfs,0);
		cout << f[0] << '\n';
	}
}

int main() {
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(20);

//  jhsy::init();

	int T = 1;
//  cin >> T;
	while (T--) {
		jhsy::main();
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3716kb

input:

4 4
1001
0100
0110
0110

output:

0

result:

wrong answer 1st numbers differ - expected: '3', found: '0'