QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#561618 | #9238. Tree | bulijiojiodibuliduo# | 0 | 501ms | 62524kb | C++17 | 2.9kb | 2024-09-13 02:02:44 | 2024-09-13 02:02:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
#ifdef ONLINE_JUDGE
#include "tree.h"
#endif
const int N=201000;
int n,lef;
vector<int> p, c;
VI son[N];
map<ll,ll> dp[N];
ll pr[N],ms[N],pl[N],lc;
vector<array<ll,3>> seg;
void init(std::vector<int> P, std::vector<int> W) {
p = P;
c = W;
n = (int)p.size();
rep(i,1,n) son[p[i]].pb(i);
rep(i,0,n) {
if (son[i].empty()) lc+=c[i];
else lc+=(ll)c[i]*(SZ(son[i])-1);
}
function<void(int)> dfs=[&](int u) {
dp[u].clear();
pl[u]=pr[u]=0;
if (son[u].empty()) {
pl[u]=1;
pr[u]=1;
return;
}
for (auto v:son[u]) {
dfs(v);
pl[u]+=pl[v];
pr[u]+=pr[v];
ms[u]+=ms[v];
if (SZ(dp[v])>SZ(dp[u])) dp[u].swap(dp[v]);
for (auto [key,val]:dp[v]) dp[u][key]+=val;
}
while (!dp[u].empty()&&prev(dp[u].end())->fi>=c[u]) {
auto it=prev(dp[u].end());
seg.pb({pl[u],pl[u]+it->se,-(it->fi-c[u])});
pl[u]+=it->se;
dp[u].erase(prev(dp[u].end()));
}
dp[u][c[u]]+=pl[u]-1; pl[u]=1;
/*while (pr[u]>R) {
ll d=min(pr[u]-R,dp[u].begin()->se);
pr[u]-=d;
if (dp[u].begin()->se==d) dp[u].erase(dp[u].begin());
else dp[u].begin()->se-=d;
}*/
};
dfs(0);
int R=pr[0];
for (auto [key,val]:dp[0]) {
seg.pb({R-val,R,-key});
R-=val;
}
}
long long query(int L, int R) {
ll ans=(ll)L*lc;
for (auto [xl,xr,w]:seg) {
xl*=L; xr*=L;
xr=min<ll>(xr,R);
if (xl<=xr) ans+=w*(xr-xl);
}
return ans;
}
#ifndef ONLINE_JUDGE
#include <cassert>
#include <cstdio>
int main() {
int N;
assert(1 == scanf("%d", &N));
std::vector<int> P(N);
P[0] = -1;
for (int i = 1; i < N; i++)
assert(1 == scanf("%d", &P[i]));
std::vector<int> W(N);
for (int i = 0; i < N; i++)
assert(1 == scanf("%d", &W[i]));
int Q;
assert(1 == scanf("%d", &Q));
std::vector<int> L(Q), R(Q);
for (int j = 0; j < Q; j++)
assert(2 == scanf("%d%d", &L[j], &R[j]));
fclose(stdin);
init(P, W);
std::vector<long long> A(Q);
for (int j = 0; j < Q; j++)
A[j] = query(L[j], R[j]);
for (int j = 0; j < Q; j++)
printf("%lld\n", A[j]);
fclose(stdout);
return 0;
}
#endif
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 40ms
memory: 54612kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 0 2 2 4 5 4 5 8 9 10 9 8 10 14 15 14 15 18 19 20 21 18 22 21 24 24 27 22 27 30 31 31 33 30 19 20 33 38 38 40 41 41 43 44 43 44 47 48 49 50 49 50 53 54 53 48 54 58 58 60 60 62 62 64 64 66 66 67 67 70 71 72 71 72 75 70 75 78 78 80 81 80 81 84 85 86 86 88 89 90...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 682659438782 834065534937 104108675609 626349038181 578226727938 1248286396644 1306138564894 417842055469 365720910400 1302029318062
result:
wrong answer 3rd lines differ - on the 1st token, expected: '682654248246', found: '682659438782'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 13
Accepted
time: 0ms
memory: 20968kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 2000 0 0 1 1 4 4 6 7 6 7 10 10 12 12 14 15 14 15 18 19 19 21 18 21 24 24 26 27 26 27 30 30 32 32 34 34 36 37 38 39 39 41 37 38 36 41 46 47 48 47 48 51 51 53 54 54 56 56 58 58 60 61 61 63 64 64 66 67 66 67 70 71 72 72 74 75 76 76 75 74 70 77 63 60 77 85 85 87 87 89 89...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 175909322571 633257447922 815909942751 39651169609 1036267874610 610572524261 164360385196 32373687020 128373030516 267765616314
result:
ok
Test #12:
score: 0
Wrong Answer
time: 0ms
memory: 21612kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 2000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 14 18 16 20 21 22 22 20 25 20 27 28 28 30 29 32 29 34 29 35 29 30 26 40 41 42 41 44 45 46 47 48 49 48 49 49 53 54 54 48 52 55 59 59 61 61 50 64 65 66 64 66 69 70 51 72 72 73 75 76 77 77 78 74 81 82 73 84 74 76 87 87 89 90...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 140057314022348 401569783286144 232681497405180 35087902070929 58132195475164 55066087812641 33888155326410 81765400104880 305768706981236 265169017767534
result:
wrong answer 3rd lines differ - on the 1st token, expected: '127351551273446', found: '140057314022348'
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 0 1 2 2 6 6 7 7 10 11 11 13 14 13 14 17 10 17 20 21 22 22 23 21 20 23 28 29 28 29 32 33 34 32 33 34 38 39 39 40 42 42 44 45 46 47 48 45 46 48 52 53 53 54 56 56 58 58 60 61 62 63 63 65 61 66 62 66 70 71 71 72 72 75 60 65 75 79 52 44 70 47 40 54 79 87 87 89 ...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Time Limit Exceeded
Test #47:
score: 22
Accepted
time: 501ms
memory: 62524kb
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 0 1 4 5 5 7 7 9 9 11 12 13 13 11 14 12 14 19 20 19 20 23 24 25 26 26 28 28 30 31 32 33 33 35 35 30 32 31 37 41 42 43 24 44 46 46 48 49 50 51 51 53 54 55 55 56 56 48 50 54 44 59 49 25 59 67 68 67 68 71 71 72 72 75 76 76 78 79 80 37 80 83 83 85 86 85 79 41 8...
output:
11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1 OK 44399242169 44212387526 45790536474 45755320631 44179830668 44674975190 45108846673 44925057561 45397405182 44060687307 44371967364 44521941379 44063691285 45721392614 44864217118 45409864033 44277589684 45749035882 45188069715 46494572380 45158343139 45090918080 ...
result:
ok
Test #48:
score: 0
Time Limit Exceeded
input:
ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0 200000 0 1 1 0 1 5 5 5 8 9 9 11 11 11 14 14 16 17 18 19 20 19 20 20 20 19 20 27 28 28 27 27 16 29 34 34 17 1 9 5 34 41 18 1 1 16 41 47 47 47 50 51 52 50 51 29 20 52 58 58 58 58 58 59 64 64 64 64 66 69 69 69 71 69 69 71 69 73 78 78 78 81 82 83 82 83 86 87 88 86 88 86 ...
output:
result:
Subtask #7:
score: 0
Skipped
Dependency #1:
0%