CSES - APIO 2012 - Results
Submission details
Task:Dispatching
Sender:henrikaalto
Submission time:2019-03-17 16:48:48 +0200
Language:C++
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED30
#2ACCEPTED70
Test results
testverdicttimegroup
#1ACCEPTED0.02 s1, 2details
#2ACCEPTED0.03 s1, 2details
#3ACCEPTED0.02 s1, 2details
#4ACCEPTED0.02 s1, 2details
#5ACCEPTED0.03 s1, 2details
#6ACCEPTED0.02 s1, 2details
#7ACCEPTED0.03 s1, 2details
#8ACCEPTED0.03 s1, 2details
#9ACCEPTED0.02 s1, 2details
#10ACCEPTED0.03 s1, 2details
#11ACCEPTED0.02 s1, 2details
#12ACCEPTED0.02 s1, 2details
#13ACCEPTED0.03 s1, 2details
#14ACCEPTED0.02 s1, 2details
#15ACCEPTED0.03 s1, 2details
#16ACCEPTED0.03 s1, 2details
#17ACCEPTED0.02 s1, 2details
#18ACCEPTED0.03 s1, 2details
#19ACCEPTED0.03 s1, 2details
#20ACCEPTED0.02 s1, 2details
#21ACCEPTED0.03 s1, 2details
#22ACCEPTED0.03 s1, 2details
#23ACCEPTED0.02 s1, 2details
#24ACCEPTED0.03 s1, 2details
#25ACCEPTED0.03 s1, 2details
#26ACCEPTED0.02 s1, 2details
#27ACCEPTED0.02 s1, 2details
#28ACCEPTED0.03 s1, 2details
#29ACCEPTED0.03 s1, 2details
#30ACCEPTED0.04 s1, 2details
#31ACCEPTED0.09 s2details
#32ACCEPTED0.14 s2details
#33ACCEPTED0.09 s2details
#34ACCEPTED0.13 s2details
#35ACCEPTED0.12 s2details
#36ACCEPTED0.14 s2details
#37ACCEPTED0.23 s2details
#38ACCEPTED0.20 s2details
#39ACCEPTED0.20 s2details
#40ACCEPTED0.18 s2details

Code

#include<bits/stdc++.h>
using namespace std;

const int N = (int) 1e5 + 1;

vector<int> v[N];

long d[N],e[N];

int n; long m;
long res = 0;

#define f first
#define s second

multiset<long> dd[N];
long amt[N];

void dfs(int x) {
  dd[x].insert(d[x]);
  amt[x] = d[x];
  for(int u : v[x]) {
    dfs(u);
    if(dd[x].size() < dd[u].size()) {
      swap(dd[x],dd[u]);
      swap(amt[x],amt[u]);
    }
    for(auto z : dd[u]) {
      dd[x].insert(z);
      amt[x] += z;
    }
  }
  while(amt[x] > m) {
    auto o = dd[x].end();
    amt[x] -= *--o;
    dd[x].erase(o);
  }
  long l = dd[x].size();
  l *= e[x];
  res = max(res,l);
/*
  cout << "node: " << x << " amt: " << amt[x] << " size: " << dd[x].size() << "\n";
  for(auto u:dd[x]) cout << u << " ";
  cout << "\n";
*/
}


int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m;
  for(int i = 1; i <= n; i++) {
    int x;
    long y,z;
    cin >> x >> y >> z;
    d[i] = y,
    e[i] = z;
    if(x != 0) {
      v[x].push_back(i);
    }
  }
  dfs(1); cout << res << "\n";
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
10 1000000000
0 1 99007575
1 2 438573466
1 2 1000000000
1 1 353443732
...

correct output
1000000000

user output
1000000000

Test 2

Group: 1, 2

Verdict: ACCEPTED

input
10 945055475
0 5366694 291855561
1 90389570 179906938
1 374697552 698585353
1 6176408 179386869
...

correct output
2918555610

user output
2918555610

Test 3

Group: 1, 2

Verdict: ACCEPTED

input
10 1000000000
0 1 200065469
1 1 86267619
2 2 252169035
3 2 442282498
...

correct output
5000000000

user output
5000000000

Test 4

Group: 1, 2

Verdict: ACCEPTED

input
10 149461880
0 19086773 254109086
1 872978 319976205
2 659016 285454579
3 1044387 215101985
...

correct output
2879785845

user output
2879785845

Test 5

Group: 1, 2

Verdict: ACCEPTED

input
10 1000000000
0 1 280411779
1 1 492376696
1 2 265769381
3 2 522023560
...

correct output
2804117790

user output
2804117790

Test 6

Group: 1, 2

Verdict: ACCEPTED

input
10 992314729
0 247471573 72238893
1 496728 403783391
1 56679 169951367
1 62461804 383546017
...

correct output
1000000000

user output
1000000000

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
10 1000000000
0 2 119191472
1 1 191898197
1 1 167040153
2 1 458449277
...

correct output
1191914720

user output
1191914720

Test 8

Group: 1, 2

Verdict: ACCEPTED

input
10 642370756
0 2000999 69581402
1 2242288 236497242
2 40562274 503433968
1 29295199 223094365
...

correct output
1182486210

user output
1182486210

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
10 1000000000
0 2 162993968
1 1 283390160
1 2 225721923
2 1 370915202
...

correct output
1629939680

user output
1629939680

Test 10

Group: 1, 2

Verdict: ACCEPTED

input
10 370763744
0 744267 91981605
1 4017320 112823498
2 2034586 349731065
1 434048 227023578
...

correct output
4000000000

user output
4000000000

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
100 1000000000
0 2 21970731
1 2 222398317
1 2 74179205
1 2 366800569
...

correct output
2197073100

user output
2197073100

Test 12

Group: 1, 2

Verdict: ACCEPTED

input
100 627156359
0 466164 39507144
1 2644648 194670076
1 438985 737387156
1 92923 226930065
...

correct output
3200078664

user output
3200078664

Test 13

Group: 1, 2

Verdict: ACCEPTED

input
100 1000000000
0 2 60428570
1 1 66827295
2 2 24238861
3 2 32334192
...

correct output
15719400724

user output
15719400724

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
100 578318939
0 5917123 49385496
1 73642 30838210
2 345236 19772120
3 1361234 33138006
...

correct output
11974219660

user output
11974219660

Test 15

Group: 1, 2

Verdict: ACCEPTED

input
100 1000000000
0 1 23430721
1 2 41155410
2 1 154924553
2 2 199287253
...

correct output
4419752888

user output
4419752888

Test 16

Group: 1, 2

Verdict: ACCEPTED

input
100 630848484
0 247658 17408547
1 6205477 34571812
2 3328020 317217034
2 509839 75788562
...

correct output
6136951750

user output
6136951750

Test 17

Group: 1, 2

Verdict: ACCEPTED

input
100 1000000000
0 1 61153166
1 2 113719784
2 1 126178940
1 2 84704700
...

correct output
6115316600

user output
6115316600

Test 18

Group: 1, 2

Verdict: ACCEPTED

input
100 407636072
0 67732 54528930
1 2021009 86259093
2 532225 75204851
3 7672116 55824152
...

correct output
4362314400

user output
4362314400

Test 19

Group: 1, 2

Verdict: ACCEPTED

input
100 1000000000
0 1 78946076
1 1 178201433
1 2 305193695
3 2 244974740
...

correct output
7894607600

user output
7894607600

Test 20

Group: 1, 2

Verdict: ACCEPTED

input
100 872316903
0 233970 44229910
1 12892849 87606228
1 51239273 284778432
3 553859 500643173
...

correct output
3767067804

user output
3767067804

Test 21

Group: 1, 2

Verdict: ACCEPTED

input
3000 1000000000
0 1 4069630
1 1 73108926
1 2 172743214
1 2 147512131
...

correct output
12208890000

user output
12208890000

Test 22

Group: 1, 2

Verdict: ACCEPTED

input
3000 249317273
0 46667 14687857
1 5272676 245994938
1 36279 97314566
1 69173951 117305676
...

correct output
12910626303

user output
12910626303

Test 23

Group: 1, 2

Verdict: ACCEPTED

input
3000 1000000000
0 1 2842710
1 1 8191203
2 1 10476640
3 2 2514314
...

correct output
51266111120

user output
51266111120

Test 24

Group: 1, 2

Verdict: ACCEPTED

input
3000 545553877
0 1112 6623376
1 55084 2983142
2 26477 2238036
3 198454 3651580
...

correct output
63153045378

user output
63153045378

Test 25

Group: 1, 2

Verdict: ACCEPTED

input
3000 1000000000
0 1 2551098
1 2 4658134
1 1 9714530
3 1 111665704
...

correct output
31822628332

user output
31822628332

Test 26

Group: 1, 2

Verdict: ACCEPTED

input
3000 627288487
0 5565 4902237
1 193311 6120910
2 884633 236261695
2 181129 206714678
...

correct output
24651134280

user output
24651134280

Test 27

Group: 1, 2

Verdict: ACCEPTED

input
3000 1000000000
0 1 1630704
1 1 1987962
2 2 5589119
3 1 7223970
...

correct output
13888769780

user output
13888769780

Test 28

Group: 1, 2

Verdict: ACCEPTED

input
3000 122350483
0 5104 6655606
1 25846 5650899
2 891 27854633
3 45821 6472808
...

correct output
10919016136

user output
10919016136

Test 29

Group: 1, 2

Verdict: ACCEPTED

input
3000 1000000000
0 2 2232598
1 1 81685454
1 2 3595234
3 1 43985678
...

correct output
8707360817

user output
8707360817

Test 30

Group: 1, 2

Verdict: ACCEPTED

input
3000 93224783
0 77920 4177581
1 781837 203726716
1 1778939 11140736
3 420662 151618788
...

correct output
7551674202

user output
7551674202

Test 31

Group: 2

Verdict: ACCEPTED

input
100000 1000000000
0 2 321236
1 2 179850797
1 2 250783699
1 2 58417453
...

correct output
32123600000

user output
32123600000

Test 32

Group: 2

Verdict: ACCEPTED

input
100000 683735612
0 176 3239903
1 7051312 109522014
1 76136860 150341229
1 136391824 64274512
...

correct output
17223324348

user output
17223324348

Test 33

Group: 2

Verdict: ACCEPTED

input
100000 1000000000
0 1 649767
1 1 96445010
1 2 439168
3 1 302538
...

correct output
310649499192

user output
310649499192

Test 34

Group: 2

Verdict: ACCEPTED

input
100000 317705311
0 206 255096
1 119 494287
2 112 858730
3 1706 695289
...

correct output
315602908920

user output
315602908920

Test 35

Group: 2

Verdict: ACCEPTED

input
100000 1000000000
0 1 336376
1 2 429262
2 2 345898
3 1 182789191
...

correct output
237426733440

user output
237426733440

Test 36

Group: 2

Verdict: ACCEPTED

input
100000 523689236
0 919 731907
1 719 1388722
2 702067 109156645
2 565641 70468645
...

correct output
69814449632

user output
69814449632

Test 37

Group: 2

Verdict: ACCEPTED

input
100000 1000000000
0 2 741680
1 2 1508388
1 1 439923
3 1 2729202
...

correct output
75493311012

user output
75493311012

Test 38

Group: 2

Verdict: ACCEPTED

input
100000 436318930
0 1491 938295
1 129 2746241
1 4122 798475
2 328 1832583
...

correct output
15408385650

user output
15408385650

Test 39

Group: 2

Verdict: ACCEPTED

input
100000 1000000000
0 1 1360440
1 2 896990
1 1 15962331
1 2 96044616
...

correct output
136044000000

user output
136044000000

Test 40

Group: 2

Verdict: ACCEPTED

input
100000 180365096
0 2318 1013091
1 180676 9091850
1 218298 10068890
2 2397728 69882120
...

correct output
7442506125

user output
7442506125