CSES - CEOI 2024, day 2

Submission details
Task:	Stations
Sender:	AH
Submission time:	2025-03-03 16:31:37 +0200
Language:	C++ (C++20)
Status:	READY
Result:	8

Feedback
group	verdict	score
#1	TIME LIMIT EXCEEDED	0
#2	ACCEPTED	8
#3	TIME LIMIT EXCEEDED	0
#4	TIME LIMIT EXCEEDED	0
#5	TIME LIMIT EXCEEDED	0
#6	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	TIME LIMIT EXCEEDED	--	1, 6	details
#2	TIME LIMIT EXCEEDED	--	1, 6	details
#3	TIME LIMIT EXCEEDED	--	1, 6	details
#4	ACCEPTED	0.01 s	1, 3, 6	details
#5	ACCEPTED	0.01 s	1, 3, 6	details
#6	ACCEPTED	0.01 s	1, 3, 6	details
#7	TIME LIMIT EXCEEDED	--	1, 6	details
#8	TIME LIMIT EXCEEDED	--	1, 6	details
#9	TIME LIMIT EXCEEDED	--	1, 6	details
#10	TIME LIMIT EXCEEDED	--	1, 6	details
#11	TIME LIMIT EXCEEDED	--	1, 6	details
#12	TIME LIMIT EXCEEDED	--	1, 6	details
#13	ACCEPTED	0.01 s	1, 2, 3, 4, 5, 6	details
#14	ACCEPTED	0.08 s	2, 3, 4, 5, 6	details
#15	TIME LIMIT EXCEEDED	--	3, 6	details
#16	TIME LIMIT EXCEEDED	--	3, 6	details
#17	TIME LIMIT EXCEEDED	--	4, 5, 6	details
#18	TIME LIMIT EXCEEDED	--	3, 4, 5, 6	details
#19	TIME LIMIT EXCEEDED	--	3, 4, 5, 6	details
#20	ACCEPTED	0.01 s	1, 3, 4, 5, 6	details
#21	TIME LIMIT EXCEEDED	--	4, 5, 6	details
#22	TIME LIMIT EXCEEDED	--	4, 5, 6	details
#23	TIME LIMIT EXCEEDED	--	4, 5, 6	details
#24	TIME LIMIT EXCEEDED	--	5, 6	details
#25	TIME LIMIT EXCEEDED	--	5, 6	details
#26	TIME LIMIT EXCEEDED	--	5, 6	details
#27	TIME LIMIT EXCEEDED	--	5, 6	details
#28	TIME LIMIT EXCEEDED	--	5, 6	details
#29	TIME LIMIT EXCEEDED	--	5, 6	details
#30	TIME LIMIT EXCEEDED	--	5, 6	details
#31	TIME LIMIT EXCEEDED	--	6	details
#32	TIME LIMIT EXCEEDED	--	6	details
#33	TIME LIMIT EXCEEDED	--	6	details
#34	TIME LIMIT EXCEEDED	--	6	details
#35	TIME LIMIT EXCEEDED	--	6	details
#36	TIME LIMIT EXCEEDED	--	6	details
#37	TIME LIMIT EXCEEDED	--	6	details
#38	TIME LIMIT EXCEEDED	--	6	details

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
 
typedef tree<int,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> index_set;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
 
#define F first
#define S second
#define PB push_back
#define EB emplace_back
#define FOR(i,a,b) for (int i = a; i < b; i++)
 
constexpr ll MOD = 1000000007;

vector<pair<ll, ll>> r[100000];
ll z[100000], f[100000], f2[100000];
pair<ll, ll> li[100000], li2[100000];
int n, k;

void mli(ll s, ll p) {
    for (auto u : r[s]) {
        if (u.F == p) continue;
        li[s] = u;
        mli(u.F, s);
    }
}

void mli2(ll s, ll p) {
    for (auto u : r[s]) {
        if (u.F == p) continue;
        li2[s] = u;
        mli2(u.F, s);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> k;
    ll b = 0, b2 = 0;
    FOR(i,0,n-1) {
        ll u, v, l; cin >> u >> v >> l;
        r[u].EB(v, l);
        r[v].EB(u, l);
        z[u]++;
        z[v]++;
    }
    FOR(i,0,n) {
        if (z[i] == 1) {
            b2 = b;
            b = i;
        }
    }
    mli(b, -1);
    mli2(b2, -1);
    li[b2] = {-1, -1};
    li2[b] = {-1, -1};
    ll csb = b;
    FOR(i,0,n) {
        if (f[csb]) {csb = li[csb].F; continue;}
        ll c = i+1, c2 = 1, ck = k, cb = csb;
        while (cb != b2) {
            if (ck - li[cb].S < 0) {
                ck = k;
                if (!f[cb]) {
                    f[cb] += (n-c) * c2;
                    c2++;
                }
                else f[cb] += (n-c) * c2;
            }
            c++;
            ck -= li[cb].S;
            cb = li[cb].F;
        }
        csb = li[csb].F;
    }

    csb = b2;
    FOR(i,0,n) {
        if (f2[csb]) {csb = li2[csb].F; continue;}
        ll c = i+1, c2 = 1, ck = k, cb = csb;
        while (cb != b) {
            if (ck - li2[cb].S < 0) {
                ck = k;
                if (!f2[cb]) {
                    f2[cb] += (n-c) * c2;
                    c2++;
                }
                else f2[cb] += (n-c) * c2;
            }
            c++;
            ck -= li2[cb].S;
            cb = li2[cb].F;
        }
        csb = li2[csb].F;
    }

    FOR(i,0,n) {
        cout << f[i] + f2[i] << "\n";
    }
}

Test details

Test 1

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`750 918 159 63 18 573 310 105 135 400 57 618 27 113 ...` view save

correct output
`0 96 45 94 0 ...` view save

user output
(empty)

Test 2

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`967 334 285 176 1 648 431 1 493 893 2 261 165 1 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 3

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 963 408 385 876 23 519 951 649 232 605 821 385 792 ...` view save

correct output
`0 0 482612 0 912 ...` view save

user output
(empty)

Test 4

Group: 1, 3, 6

Verdict: ACCEPTED

input
`1000 396 412 257 190 290 965 25 399 938 174 980 459 117 ...` view save

correct output
`215160 138947 196491 47632 103775 ...` view save

user output
`215160 138947 196491 47632 103775 ...` Truncated

Test 5

Group: 1, 3, 6

Verdict: ACCEPTED

input
`1000 333 896 853 0 28 756 0 658 183 0 488 17 0 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
`0 0 0 0 0 ...` Truncated

Test 6

Group: 1, 3, 6

Verdict: ACCEPTED

input
`2 31 0 1 31` view save

correct output
`0 0` view save

user output
`0 0` view save

Test 7

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 847 24 298 474 208 141 485 789 89 60 1 809 437 ...` view save

correct output
`16 1080 1966 5980 1856 ...` view save

user output
(empty)

Test 8

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 767 476 799 361 271 239 215 447 941 269 219 664 600 ...` view save

correct output
`1017 997 3988 1996 0 ...` view save

user output
(empty)

Test 9

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 574 351 479 444 634 559 531 70 113 180 828 194 ...` view save

correct output
`17839 4922 3988 0 0 ...` view save

user output
(empty)

Test 10

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 680 881 340 73 368 929 303 239 219 861 605 561 ...` view save

correct output
`88 3990 9954 0 0 ...` view save

user output
(empty)

Test 11

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 1000 164 378 963 934 141 358 866 915 598 341 220 55 ...` view save

correct output
`1996 0 1147 1996 18739 ...` view save

user output
(empty)

Test 12

Group: 1, 6

Verdict: TIME LIMIT EXCEEDED

input
`1000 537 276 155 470 533 155 391 175 155 343 553 155 270 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 13

Group: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`2 1 0 1 1` view save

correct output
`0 0` view save

user output
`0 0` view save

Test 14

Group: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`70000 1 50913 18377 1 33894 11911 1 61940 7863 1 61602 33470 1 ...` view save

correct output
`2128187656 1918647796 1539693556 1198079316 2227641388 ...` view save

user output
`2128187656 1918647796 1539693556 1198079316 2227641388 ...` Truncated

Test 15

Group: 3, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 517272873 57335 18148 62837135 28239 56484 253183094 23004 59130 129215861 558 17489 52424960 ...` view save

correct output
`450859 215263283 544492560 222149 1276050 ...` view save

user output
(empty)

Test 16

Group: 3, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 611016790 21272 16063 50360 30758 33429 30642 23317 5625 9045 66335 5731 24130 ...` view save

correct output
`69999 102210 23584 30220 0 ...` view save

user output
(empty)

Test 17

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`69973 4 44281 27162 1 15299 61302 1 19250 66379 1 45970 65938 1 ...` view save

correct output
`769608 34960 1162375 626228 2 ...` view save

user output
(empty)

Test 18

Group: 3, 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 6 12580 20937 2 31244 33335 1 62095 66946 0 2558 64306 2 ...` view save

correct output
`95678 275287413 81937227 47960445 176569 ...` view save

user output
(empty)

Test 19

Group: 3, 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 45546 20793 0 44801 49720 0 54732 9736 0 64375 18647 0 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 20

Group: 1, 3, 4, 5, 6

Verdict: ACCEPTED

input
`2 6 0 1 6` view save

correct output
`0 0` view save

user output
`0 0` view save

Test 21

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 36906 67900 2 51465 24882 0 65531 32406 0 49018 50640 10 ...` view save

correct output
`0 0 1141061037 69997 0 ...` view save

user output
(empty)

Test 22

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 40966 26929 6 15381 7596 3 53090 61576 3 6976 65087 2 ...` view save

correct output
`279988 0 0 56174160 0 ...` view save

user output
(empty)

Test 23

Group: 4, 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 47111 32841 10 510 5994 10 1362 44478 8 61688 30984 5 ...` view save

correct output
`419980 0 979765 0 1679710 ...` view save

user output
(empty)

Test 24

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 7 12257 45873 7 53771 24407 7 67182 59338 2 68981 59097 6 ...` view save

correct output
`0 0 0 0 56749 ...` view save

user output
(empty)

Test 25

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 7 60987 29710 2 40235 14667 3 49803 36218 0 1256 23603 0 ...` view save

correct output
`559942 0 69996 0 0 ...` view save

user output
(empty)

Test 26

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 4 29827 12474 3 52717 68608 1 26411 5022 3 66140 68360 2 ...` view save

correct output
`419970 0 0 202 0 ...` view save

user output
(empty)

Test 27

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 41642 65096 7 14235 28073 6 48132 705 7 23384 33897 0 ...` view save

correct output
`139996 279988 0 0 0 ...` view save

user output
(empty)

Test 28

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 44002 46661 10 16351 40057 10 62342 69569 2 277 38372 1 ...` view save

correct output
`0 0 559966 0 0 ...` view save

user output
(empty)

Test 29

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 10 11173 32861 3 13926 50906 10 18305 60850 3 13279 836 9 ...` view save

correct output
`0 139996 2 0 0 ...` view save

user output
(empty)

Test 30

Group: 5, 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 3 18748 12670 2 56209 12670 2 4918 12670 1 26713 12670 2 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 31

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`67845 886519666 14071 38244 390226 23927 10508 4649507 24776 60617 7933069 44979 29276 6727041 ...` view save

correct output
`43 0 395 0 81 ...` view save

user output
(empty)

Test 32

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 598182175 35387 18369 177725639 34272 27820 390474503 14996 60451 566274308 31897 35730 516503530 ...` view save

correct output
`0 0 0 2373343036 2449703732 ...` view save

user output
(empty)

Test 33

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 307114024 18 68382 208881990 51105 51287 133487858 6935 48425 203987749 30063 35675 238707761 ...` view save

correct output
`0 5457705 0 420055 0 ...` view save

user output
(empty)

Test 34

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 260495634 10465 32381 229572819 59714 8684 92922283 44269 63680 232833764 47600 15978 126514599 ...` view save

correct output
`350035 839810 1 0 477281 ...` view save

user output
(empty)

Test 35

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 1000000000 40606 60962 166792 66689 16700 510579 39392 42623 271902 12827 150 783709 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 36

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 1000000000 18028 63559 764765 43037 44898 469661 22315 22254 359926 32987 69384 314936 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 37

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 1000000000 48195 15915 457746 7436 2784 442186 9122 3611 587852 31354 12943 476363 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

Test 38

Group: 6

Verdict: TIME LIMIT EXCEEDED

input
`70000 852351984 54341 29527 743304598 55902 29527 379127182 8584 29527 326761145 21272 29527 850588761 ...` view save

correct output
`0 0 0 0 0 ...` view save

user output
(empty)

CEOI 2024, day 2

Stations

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

Tasks

Submissions (AH)