CSES - APIO 2012

Submission details
Task:	Dispatching
Sender:	ArktinenKarpalo
Submission time:	2019-03-17 14:46:05 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	30
#2	ACCEPTED	70

Test results
test	verdict	time	group
#1	ACCEPTED	0.03 s	1, 2	details
#2	ACCEPTED	0.03 s	1, 2	details
#3	ACCEPTED	0.04 s	1, 2	details
#4	ACCEPTED	0.04 s	1, 2	details
#5	ACCEPTED	0.04 s	1, 2	details
#6	ACCEPTED	0.03 s	1, 2	details
#7	ACCEPTED	0.03 s	1, 2	details
#8	ACCEPTED	0.04 s	1, 2	details
#9	ACCEPTED	0.03 s	1, 2	details
#10	ACCEPTED	0.04 s	1, 2	details
#11	ACCEPTED	0.04 s	1, 2	details
#12	ACCEPTED	0.03 s	1, 2	details
#13	ACCEPTED	0.03 s	1, 2	details
#14	ACCEPTED	0.03 s	1, 2	details
#15	ACCEPTED	0.03 s	1, 2	details
#16	ACCEPTED	0.03 s	1, 2	details
#17	ACCEPTED	0.04 s	1, 2	details
#18	ACCEPTED	0.04 s	1, 2	details
#19	ACCEPTED	0.03 s	1, 2	details
#20	ACCEPTED	0.03 s	1, 2	details
#21	ACCEPTED	0.03 s	1, 2	details
#22	ACCEPTED	0.04 s	1, 2	details
#23	ACCEPTED	0.04 s	1, 2	details
#24	ACCEPTED	0.04 s	1, 2	details
#25	ACCEPTED	0.03 s	1, 2	details
#26	ACCEPTED	0.03 s	1, 2	details
#27	ACCEPTED	0.03 s	1, 2	details
#28	ACCEPTED	0.04 s	1, 2	details
#29	ACCEPTED	0.04 s	1, 2	details
#30	ACCEPTED	0.05 s	1, 2	details
#31	ACCEPTED	0.09 s	2	details
#32	ACCEPTED	0.15 s	2	details
#33	ACCEPTED	0.09 s	2	details
#34	ACCEPTED	0.13 s	2	details
#35	ACCEPTED	0.10 s	2	details
#36	ACCEPTED	0.14 s	2	details
#37	ACCEPTED	0.23 s	2	details
#38	ACCEPTED	0.29 s	2	details
#39	ACCEPTED	0.18 s	2	details
#40	ACCEPTED	0.23 s	2	details

Code

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N (1<<18)
#define M 100000007
#define P complex<long long>
#define X real()
#define Y imag()

using namespace std;

int n, m, p[101010], c[101010], lvl[101010], koko[101010], sn[101010], scnt;
multiset<int> sm[101010], sp[101010];
ll ans, smC[101010], l[101010];
vector<int> taso[101010];

int main() {
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for(int i=1; i<=n; i++) {
		cin >> p[i] >> c[i] >> l[i];
		lvl[i] = lvl[p[i]]+1;
		taso[lvl[i]].push_back(i);
	}

	for(int i=n; i>=1; i--) {
		for(auto u:taso[i]) {
			if(!sn[u]) {
				scnt++;
				sn[u] = scnt;
			}
			sm[sn[u]].insert(c[u]);
			smC[sn[u]] += c[u];
			while(smC[sn[u]] > m) {
				auto it = prev(sm[sn[u]].end(), 1);
				smC[sn[u]] -= *it;
				sp[sn[u]].insert(*it);
				sm[sn[u]].erase(it);
			}
			while(sm[sn[u]].size() > 0 && sp[sn[u]].size() > 0) {
				auto it = prev(sm[sn[u]].end(), 1);
				auto it2 = sp[sn[u]].begin();
				if(*it2 < *it) {
					smC[sn[u]] += (-*it) + (*it2);
					int luku = *it;
					sm[sn[u]].erase(it);
					sm[sn[u]].insert(*it2);
					sp[sn[u]].erase(it2);
					sp[sn[u]].insert(luku);
				} else {
					break;
				}
			}
			while(smC[sn[u]] < m && sp[sn[u]].size() > 0) {
				auto it = sp[sn[u]].begin();
				if(smC[sn[u]] + *it <= m) {
					smC[sn[u]] += *it;
					sm[sn[u]].insert(*it);
					sp[sn[u]].erase(it);
				} else {
					break;
				}
			}
			ans = max(ans, (ll)(l[u]*sm[sn[u]].size()));
			koko[u]++;
			if(koko[u] > koko[p[u]]) {
				for(auto uu:sm[sn[p[u]]]) {
					sm[sn[u]].insert(uu);
				}
				for(auto uu:sp[sn[p[u]]]) {
					sp[sn[u]].insert(uu);
				}
				smC[sn[u]] += smC[sn[p[u]]];
				sm[sn[p[u]]].clear();
				sp[sn[p[u]]].clear();
				sn[p[u]] = sn[u];
			} else {
				for(auto uu:sm[sn[u]]) {
					sm[sn[p[u]]].insert(uu);
				}
				for(auto uu:sp[sn[u]]) {
					sp[sn[p[u]]].insert(uu);
				}
				smC[sn[p[u]]] += smC[sn[u]];
				sm[sn[u]].clear();
				sp[sn[u]].clear();
			}
			koko[p[u]] += koko[u];
		}
	}
	cout << ans;
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
`10 1000000000 0 1 99007575 1 2 438573466 1 2 1000000000 1 1 353443732 ...` view save

correct output
`1000000000` view save

user output
`1000000000` view save

Test 2

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`2918555610` view save

user output
`2918555610` view save

Test 3

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`5000000000` view save

user output
`5000000000` view save

Test 4

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`2879785845` view save

user output
`2879785845` view save

Test 5

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`2804117790` view save

user output
`2804117790` view save

Test 6

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`1000000000` view save

user output
`1000000000` view save

Test 7

Group: 1, 2

Verdict: ACCEPTED

input
`10 1000000000 0 2 119191472 1 1 191898197 1 1 167040153 2 1 458449277 ...` view save

correct output
`1191914720` view save

user output
`1191914720` view save

Test 8

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`1182486210` view save

user output
`1182486210` view save

Test 9

Group: 1, 2

Verdict: ACCEPTED

input
`10 1000000000 0 2 162993968 1 1 283390160 1 2 225721923 2 1 370915202 ...` view save

correct output
`1629939680` view save

user output
`1629939680` view save

Test 10

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`4000000000` view save

user output
`4000000000` view save

Test 11

Group: 1, 2

Verdict: ACCEPTED

input
`100 1000000000 0 2 21970731 1 2 222398317 1 2 74179205 1 2 366800569 ...` view save

correct output
`2197073100` view save

user output
`2197073100` view save

Test 12

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`3200078664` view save

user output
`3200078664` view save

Test 13

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`15719400724` view save

user output
`15719400724` view save

Test 14

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`11974219660` view save

user output
`11974219660` view save

Test 15

Group: 1, 2

Verdict: ACCEPTED

input
`100 1000000000 0 1 23430721 1 2 41155410 2 1 154924553 2 2 199287253 ...` view save

correct output
`4419752888` view save

user output
`4419752888` view save

Test 16

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`6136951750` view save

user output
`6136951750` view save

Test 17

Group: 1, 2

Verdict: ACCEPTED

input
`100 1000000000 0 1 61153166 1 2 113719784 2 1 126178940 1 2 84704700 ...` view save

correct output
`6115316600` view save

user output
`6115316600` view save

Test 18

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`4362314400` view save

user output
`4362314400` view save

Test 19

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`7894607600` view save

user output
`7894607600` view save

Test 20

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`3767067804` view save

user output
`3767067804` view save

Test 21

Group: 1, 2

Verdict: ACCEPTED

input
`3000 1000000000 0 1 4069630 1 1 73108926 1 2 172743214 1 2 147512131 ...` view save

correct output
`12208890000` view save

user output
`12208890000` view save

Test 22

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`12910626303` view save

user output
`12910626303` view save

Test 23

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`51266111120` view save

user output
`51266111120` view save

Test 24

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`63153045378` view save

user output
`63153045378` view save

Test 25

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`31822628332` view save

user output
`31822628332` view save

Test 26

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`24651134280` view save

user output
`24651134280` view save

Test 27

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`13888769780` view save

user output
`13888769780` view save

Test 28

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`10919016136` view save

user output
`10919016136` view save

Test 29

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`8707360817` view save

user output
`8707360817` view save

Test 30

Group: 1, 2

Verdict: ACCEPTED

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

correct output
`7551674202` view save

user output
`7551674202` view save

Test 31

Group: 2

Verdict: ACCEPTED

input
`100000 1000000000 0 2 321236 1 2 179850797 1 2 250783699 1 2 58417453 ...` view save

correct output
`32123600000` view save

user output
`32123600000` view save

Test 32

Group: 2

Verdict: ACCEPTED

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

correct output
`17223324348` view save

user output
`17223324348` view save

Test 33

Group: 2

Verdict: ACCEPTED

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

correct output
`310649499192` view save

user output
`310649499192` view save

Test 34

Group: 2

Verdict: ACCEPTED

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

correct output
`315602908920` view save

user output
`315602908920` view save

Test 35

Group: 2

Verdict: ACCEPTED

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

correct output
`237426733440` view save

user output
`237426733440` view save

Test 36

Group: 2

Verdict: ACCEPTED

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

correct output
`69814449632` view save

user output
`69814449632` view save

Test 37

Group: 2

Verdict: ACCEPTED

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

correct output
`75493311012` view save

user output
`75493311012` view save

Test 38

Group: 2

Verdict: ACCEPTED

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

correct output
`15408385650` view save

user output
`15408385650` view save

Test 39

Group: 2

Verdict: ACCEPTED

input
`100000 1000000000 0 1 1360440 1 2 896990 1 1 15962331 1 2 96044616 ...` view save

correct output
`136044000000` view save

user output
`136044000000` view save

Test 40

Group: 2

Verdict: ACCEPTED

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

correct output
`7442506125` view save

user output
`7442506125` view save

APIO 2012

Dispatching

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Tasks

Submissions (ArktinenKarpalo)