QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#597143 | #9132. Painting Fences | ucup-team2432# | WA | 0ms | 3716kb | C++20 | 4.3kb | 2024-09-28 17:09:26 | 2024-09-28 17:09:28 |
Judging History
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'