QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#561609#9238. Treebulijiojiodibuliduo#0 110ms48140kbC++172.6kb2024-09-13 01:36:012024-09-13 01:36:02

Judging History

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

  • [2024-09-13 01:36:02]
  • 评测
  • 测评结果:0
  • 用时:110ms
  • 内存:48140kb
  • [2024-09-13 01:36:01]
  • 提交

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];

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);
}

long long query(int L, int R) {
  ll ans=0;
  function<void(int)> dfs=[&](int u) {
    dp[u].clear();
    pl[u]=pr[u]=0;
    if (son[u].empty()) {
      pl[u]=L;
      pr[u]=L;
      ans+=(ll)L*c[u];
      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].begin())->fi>=c[u]) {
      pl[u]+=prev(dp[u].begin())->se;
      dp[u].erase(prev(dp[u].begin()));
    }
    dp[u][c[u]]+=pl[u]-L; pl[u]=L;
    while (pr[u]>R) {
      ll d=min(pr[u]-R,dp[u].begin()->se);
      pr[u]-=d;
      ans+=d*dp[u].begin()->fi;
      if (dp[u].begin()->se==d) dp[u].erase(dp[u].begin());
      else dp[u].begin()->se-=d;
    }
    //printf("!! u %d pl %lld pr %lld ms %lld\n",u,pl[u],pr[u],ms[u]);
  };
  dfs(0);
  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
Runtime Error

Test #1:

score: 10
Accepted
time: 110ms
memory: 48140kb

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
682654248246
834059146585
104107877065
626344246917
578222335946
1248276814116
1306128583094
417838861293
365718115496
1302019336262

result:

ok 

Test #2:

score: 10
Accepted
time: 96ms
memory: 48064kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
200000
0 0 2 2 4 5 6 7 7 9 9 11 12 11 5 13 12 6 4 13 20 21 20 21 24 25 25 27 28 27 28 29 32 32 34 35 36 36 37 34 39 41 39 35 37 42 41 42 48 48 50 50 52 52 54 54 56 57 58 58 56 59 59 63 63 65 66 65 57 66 70 70 72 73 73 75 72 75 78 78 80 80 81 83 83 84 81 29 24 84 90 9...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
2412828
1922117
1327147
965330
1085799
1564240
1690944
1688948
2415056
1441542

result:

ok 

Test #3:

score: 10
Accepted
time: 83ms
memory: 36608kb

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
200000
0 0 0 3 4 5 4 4 5 5 10 10 10 13 13 15 15 15 18 3 5 5 18 23 24 24 25 27 27 27 27 31 32 33 32 33 33 33 38 38 38 41 41 38 32 38 38 41 48 48 50 50 50 53 53 55 55 55 48 55 60 60 55 61 64 64 64 64 53 64 55 64 72 72 72 50 48 72 78 78 80 81 81 81 81 83 86 86 86 86 88 ...

output:

11XNDQnkdGXK8y3iaqfMvWKu4vqrBbz1
OK
57510536913265758
13893873797083323
19946610899128
612378945455168
5805050629165603
24375661619556703
36105231950324439
45342443221065693
18169686485050308
12956499749658231

result:

ok 

Test #4:

score: 0
Runtime Error

input:

ZYKrr4gCMcKeyfk6kbZU5k4ZyW3sAGT0
200000
0 1 2 3 4 5 6 7 8 9 9 10 12 13 14 14 13 17 15 19 20 21 21 22 22 25 26 27 27 29 30 30 32 32 34 35 36 37 36 38 40 41 42 43 44 38 36 40 48 49 49 51 52 53 53 52 56 57 55 57 59 61 62 63 64 65 66 63 68 69 69 71 67 73 73 74 76 77 76 76 80 80 82 83 80 75 86 77 88 89 9...

output:


result:


Subtask #2:

score: 0
Wrong Answer

Test #11:

score: 13
Accepted
time: 0ms
memory: 20256kb

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: 21536kb

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
142508132747904
400393526117904
230879863061930
42462540502583
68232897824517
71458194592473
33626652105585
80989150204230
304539067433526
264637231660269

result:

wrong answer 3rd lines differ - on the 1st token, expected: '127351551273446', found: '142508132747904'

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: 0
Time Limit Exceeded

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:


result:


Subtask #7:

score: 0
Skipped

Dependency #1:

0%