CSES - Leirikisa 2

CSES - Leirikisa 2 - Results

Submission details
Task:	Alpine valley
Sender:	DualRed
Submission time:	2023-04-18 16:08:54 +0300
Language:	C++ (C++20)
Status:	READY
Result:	59

Feedback
group	verdict	score
#1	ACCEPTED	9
#2	ACCEPTED	27
#3	ACCEPTED	23
#4	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	2, 4	details
#2	ACCEPTED	0.01 s	2, 4	details
#3	ACCEPTED	0.01 s	1, 4	details
#4	ACCEPTED	0.01 s	1, 4	details
#5	ACCEPTED	0.01 s	1, 4	details
#6	ACCEPTED	0.01 s	1, 3, 4	details
#7	ACCEPTED	0.01 s	2, 4	details
#8	ACCEPTED	0.01 s	2, 4	details
#9	ACCEPTED	0.01 s	2, 4	details
#10	ACCEPTED	0.01 s	2, 4	details
#11	ACCEPTED	0.01 s	2, 4	details
#12	ACCEPTED	0.01 s	2, 4	details
#13	ACCEPTED	0.01 s	2, 3, 4	details
#14	ACCEPTED	0.01 s	2, 3, 4	details
#15	ACCEPTED	0.01 s	2, 3, 4	details
#16	ACCEPTED	0.02 s	2, 4	details
#17	ACCEPTED	0.15 s	3, 4	details
#18	ACCEPTED	0.16 s	3, 4	details
#19	ACCEPTED	0.17 s	3, 4	details
#20	ACCEPTED	0.19 s	3, 4	details
#21	ACCEPTED	0.16 s	3, 4	details
#22	ACCEPTED	0.20 s	3, 4	details
#23	ACCEPTED	0.20 s	4	details
#24	ACCEPTED	0.35 s	4	details
#25	ACCEPTED	2.38 s	4	details
#26	TIME LIMIT EXCEEDED	--	4	details
#27	TIME LIMIT EXCEEDED	--	4	details
#28	ACCEPTED	0.17 s	4	details
#29	ACCEPTED	0.22 s	4	details
#30	ACCEPTED	0.56 s	4	details
#31	ACCEPTED	2.13 s	4	details
#32	ACCEPTED	2.61 s	4	details
#33	ACCEPTED	0.15 s	4	details
#34	ACCEPTED	0.17 s	4	details
#35	ACCEPTED	0.19 s	4	details
#36	ACCEPTED	0.24 s	4	details
#37	ACCEPTED	0.21 s	4	details
#38	TIME LIMIT EXCEEDED	--	4	details

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N = 1e5+7;
vector<pair<int, ll>> v[N];
bool is_shop[N];
bool has_shop[N];
int e[N][20];
int depth[N];

void dfs(int i, int pr, int d){
    e[i][0] = pr;
    depth[i] = d;
    for(auto p : v[i]){
        int j = p.first; //int w = p.second;
        if(j == pr) continue;
        dfs(j, i, d+1);
        if(has_shop[j]) has_shop[i] = true;
    }
}



int main(){
    cin.tie(0)->sync_with_stdio(0);

    int N, S, Q, E;
    cin >> N >> S >> Q >> E;
    vector<pair<int, int>> roads(N+3);
    for(int i = 1; i < N; i++){
        int A, B; ll W;
        cin >> A >> B >> W;
        v[A].push_back(make_pair(B, W));
        v[B].push_back(make_pair(A, W));
        roads[i] = make_pair(A, B);
    }
    for(int i = 0; i < S; i++){
        int x; cin >> x;
        is_shop[x] = true;
        has_shop[x] = true;
    }

    dfs(E, E, 0);

    for(int b = 1; b < 20; b++){
        for(int i = 1; i <= N; i++){
            e[i][b] = e[e[i][b-1]][b-1];
        }
    }

    for(int i = 0; i < Q; i++){
        int I, R;
        cin >> I >> R;
        int a = roads[I].first;
        int b = roads[I].second;
        if(depth[a] > depth[b]) swap(a, b);
        assert(depth[a]+1==depth[b]);

        bool impossible = false;
        if(depth[R] >= depth[b]){
            int k = depth[R] - depth[b];
            int r = R;
            int jmp = 0;
            while(k){
                if(k & 1) r = e[r][jmp];
                jmp++;
                k >>= 1;
            }
            if(r == b) impossible = true;
        }
        if(!impossible){
            cout << "escaped\n";
            continue;
        }

        /*if(!has_shop[b]){
            cout << "oo\n";
            continue;
        }*/

        ll ans = -1;
        priority_queue<pair<ll, int>> q;
        vector<bool> visited(N+3, false);
        q.push(make_pair(0, R));
        while(q.size() > 0){
            auto p = q.top(); q.pop();
            int x = p.second;
            if(visited[x]) continue;
            visited[x] = true;
            ll cost = -p.first;
            if(is_shop[x]){
                ans = cost;
                break;
            }

            for(auto pp : v[x]){
                int y = pp.first;
                int w = pp.second;
                if(x == b && y == a) continue;
                if(visited[y]) continue;
                q.push(make_pair(-(cost + w), y));
            }
        }

        if(ans != -1) cout << ans << "\n";
        else cout << "oo\n";
    }





}

Test details

Test 1

Group: 2, 4

Verdict: ACCEPTED

input
`5 2 3 1 1 2 3 1 3 2 3 4 1 3 5 2 ...` view save

correct output
`escaped 3 oo` view save

user output
`escaped 3 oo` view save

Test 2

Group: 2, 4

Verdict: ACCEPTED

input
`10 2 5 4 7 2 3 4 8 3 9 10 1 6 7 3 ...` view save

correct output
`8 escaped escaped escaped 0` view save

user output
`8 escaped escaped escaped 0` view save

Test 3

Group: 1, 4

Verdict: ACCEPTED

input
`100 1 10000 16 55 54 51 52 51 42 61 60 65 8 7 2 ...` view save

correct output
`escaped 556 102 escaped escaped ...` view save

user output
`escaped 556 102 escaped escaped ...` Truncated

Test 4

Group: 1, 4

Verdict: ACCEPTED

input
`100 10 10000 33 9 8 121427413 62 61 566068708 54 53 965740432 15 14 900558622 ...` view save

correct output
`escaped escaped escaped escaped escaped ...` view save

user output
`escaped escaped escaped escaped escaped ...` Truncated

Test 5

Group: 1, 4

Verdict: ACCEPTED

input
`100 50 10000 41 50 49 169637902 97 96 415399500 21 20 685901242 80 79 491260472 ...` view save

correct output
`escaped escaped escaped 0 236683917 ...` view save

user output
`escaped escaped escaped 0 236683917 ...` Truncated

Test 6

Group: 1, 3, 4

Verdict: ACCEPTED

input
`100 100 10000 72 72 71 184167801 54 53 889251906 84 83 405385709 60 59 13704743 ...` view save

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

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

Test 7

Group: 2, 4

Verdict: ACCEPTED

input
`1000 10 1000 775 118 928 460113608 474 70 44866463 733 393 759680660 710 206 648722901 ...` view save

correct output
`oo escaped escaped escaped escaped ...` view save

user output
`oo escaped escaped escaped escaped ...` Truncated

Test 8

Group: 2, 4

Verdict: ACCEPTED

input
`1000 10 1000 327 723 162 446180859 68 802 80310794 102 267 312376651 107 624 882387970 ...` view save

correct output
`oo escaped oo escaped escaped ...` view save

user output
`oo escaped oo escaped escaped ...` Truncated

Test 9

Group: 2, 4

Verdict: ACCEPTED

input
`1000 10 1000 650 119 161 836736621 838 410 854228864 199 424 454768400 60 883 388702647 ...` view save

correct output
`escaped escaped escaped escaped escaped ...` view save

user output
`escaped escaped escaped escaped escaped ...` Truncated

Test 10

Group: 2, 4

Verdict: ACCEPTED

input
`1000 100 1000 904 68 170 85699385 237 651 740139463 43 176 201438090 106 79 819260668 ...` view save

correct output
`escaped oo escaped 1775619050 escaped ...` view save

user output
`escaped oo escaped 1775619050 escaped ...` Truncated

Test 11

Group: 2, 4

Verdict: ACCEPTED

input
`1000 100 1000 529 463 789 845004864 358 945 244505855 758 337 184497598 576 316 809439021 ...` view save

correct output
`escaped 0 696530048 oo escaped ...` view save

user output
`escaped 0 696530048 oo escaped ...` Truncated

Test 12

Group: 2, 4

Verdict: ACCEPTED

input
`1000 100 1000 399 347 194 896931732 85 77 502917238 383 704 495548440 249 529 89377715 ...` view save

correct output
`escaped 1803283908 escaped escaped 725025384 ...` view save

user output
`escaped 1803283908 escaped escaped 725025384 ...` Truncated

Test 13

Group: 2, 3, 4

Verdict: ACCEPTED

input
`1000 1000 1000 417 955 976 76162239 18 206 157439239 568 995 870854038 144 131 177990967 ...` view save

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

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

Test 14

Group: 2, 3, 4

Verdict: ACCEPTED

input
`1000 1000 1000 5 499 981 674767192 867 11 231983677 289 607 850347433 90 435 109149869 ...` view save

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

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

Test 15

Group: 2, 3, 4

Verdict: ACCEPTED

input
`1000 1000 1000 402 827 566 831751863 177 338 737463577 130 290 477228687 381 865 208330027 ...` view save

correct output
`escaped escaped escaped escaped escaped ...` view save

user output
`escaped escaped escaped escaped escaped ...` Truncated

Test 16

Group: 2, 4

Verdict: ACCEPTED

input
`1000 250 1000 719 955 478 999987900 118 129 1 693 642 1 89 10 1 ...` view save

correct output
`escaped escaped escaped 999977335 999996043 ...` view save

user output
`escaped escaped escaped 999977335 999996043 ...` Truncated

Test 17

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 100000 12006 92983 79841 908116525 62826 38940 643240290 40394 33248 544303480 39790 52014 996656288 ...` view save

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

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

Test 18

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 100000 43094 5443 54581 582924938 89476 92046 904127360 75423 44348 666119170 81404 62453 705128933 ...` view save

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

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

Test 19

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 100000 9488 85370 19201 696298836 18577 46570 748157745 93114 16265 496529753 72078 35717 412237533 ...` view save

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

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

Test 20

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 100000 92001 67551 36343 183011569 68768 16547 690994742 13471 67372 20695710 98903 83909 529919884 ...` view save

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

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

Test 21

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 100000 63926 18158 65925 685699704 99966 63209 722194632 56258 49447 38979748 29360 52524 25423329 ...` view save

correct output
`escaped escaped escaped escaped escaped ...` view save

user output
`escaped escaped escaped escaped escaped ...` Truncated

Test 22

Group: 3, 4

Verdict: ACCEPTED

input
`100000 100000 100000 85193 49261 94283 81875369 4550 87086 277612782 72700 32371 96444536 35214 5979 709167976 ...` view save

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

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

Test 23

Group: 4

Verdict: ACCEPTED

input
`100000 1 100000 62049 75022 73793 917598653 23223 74953 213701558 70480 94902 210482731 33079 67728 721615672 ...` view save

correct output
`escaped oo oo oo oo ...` view save

user output
`escaped oo oo oo oo ...` Truncated

Test 24

Group: 4

Verdict: ACCEPTED

input
`100000 1 100000 60683 9762 13929 907620072 89241 80927 134733122 82965 83054 398493573 4190 85710 220472721 ...` view save

correct output
`escaped escaped escaped oo oo ...` view save

user output
`escaped escaped escaped oo oo ...` Truncated

Test 25

Group: 4

Verdict: ACCEPTED

input
`100000 1 100000 93416 42120 30969 334590602 10610 91725 333854906 42083 81502 240679835 46376 56414 480503067 ...` view save

correct output
`oo escaped escaped oo escaped ...` view save

user output
`oo escaped escaped oo escaped ...` Truncated

Test 26

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
`100000 1 100000 49260 46043 27573 782901085 51894 53168 613136964 51695 80449 302924017 93824 72798 926998901 ...` view save

correct output
`escaped oo oo escaped oo ...` view save

user output
(empty)

Test 27

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
`100000 1 100000 48778 3031 66280 306595565 79785 6125 348382536 94956 48606 123996452 55800 22463 47341587 ...` view save

correct output
`20156757703441 escaped 20262827699543 escaped escaped ...` view save

user output
(empty)

Test 28

Group: 4

Verdict: ACCEPTED

input
`100000 100 100000 45904 91930 987 534423336 39029 44466 55162879 2591 7401 202591700 39136 56566 892409583 ...` view save

correct output
`escaped escaped oo escaped escaped ...` view save

user output
`escaped escaped oo escaped escaped ...` Truncated

Test 29

Group: 4

Verdict: ACCEPTED

input
`100000 100 100000 52351 4136 69049 98258152 1792 36401 226432996 75376 71266 993314697 69397 76013 629006800 ...` view save

correct output
`oo escaped escaped escaped oo ...` view save

user output
`oo escaped escaped escaped oo ...` Truncated

Test 30

Group: 4

Verdict: ACCEPTED

input
`100000 100 100000 53445 34402 59905 406487655 56698 75242 807833720 81339 68024 45910238 65317 68290 1780385 ...` view save

correct output
`oo escaped escaped escaped escaped ...` view save

user output
`oo escaped escaped escaped escaped ...` Truncated

Test 31

Group: 4

Verdict: ACCEPTED

input
`100000 100 100000 47731 54332 9781 136759305 68411 656 232175662 94782 84387 638037402 32454 10432 915608818 ...` view save

correct output
`escaped escaped oo escaped oo ...` view save

user output
`escaped escaped oo escaped oo ...` Truncated

Test 32

Group: 4

Verdict: ACCEPTED

input
`100000 100 100000 93400 41569 42438 321398411 49592 36193 851003327 97175 8604 619586051 49225 51930 774715298 ...` view save

correct output
`escaped escaped escaped escaped 169890887130 ...` view save

user output
`escaped escaped escaped escaped 169890887130 ...` Truncated

Test 33

Group: 4

Verdict: ACCEPTED

input
`100000 10000 100000 93612 38831 95327 244435916 89221 84478 457809450 19641 22100 136197388 30274 55704 225978648 ...` view save

correct output
`escaped oo oo escaped escaped ...` view save

user output
`escaped oo oo escaped escaped ...` Truncated

Test 34

Group: 4

Verdict: ACCEPTED

input
`100000 10000 100000 87842 98378 17648 944109570 15907 38157 120262987 22016 83274 39186354 60388 31304 479667455 ...` view save

correct output
`escaped 1139182192 1232429781 0 oo ...` view save

user output
`escaped 1139182192 1232429781 0 oo ...` Truncated

Test 35

Group: 4

Verdict: ACCEPTED

input
`100000 10000 100000 67190 83252 69978 629862602 59544 15851 9101373 65114 24734 594009368 80279 35421 30446439 ...` view save

correct output
`escaped escaped oo escaped oo ...` view save

user output
`escaped escaped oo escaped oo ...` Truncated

Test 36

Group: 4

Verdict: ACCEPTED

input
`100000 10000 100000 99161 72942 44990 542188499 43085 52327 474981003 35672 65958 618901863 47062 48069 864393688 ...` view save

correct output
`escaped 653059479 escaped escaped 0 ...` view save

user output
`escaped 653059479 escaped escaped 0 ...` Truncated

Test 37

Group: 4

Verdict: ACCEPTED

input
`100000 10000 100000 10932 61909 89572 45368675 5240 30566 274286750 59949 57340 817361702 76233 22765 595831327 ...` view save

correct output
`escaped escaped escaped 832606240 530619380 ...` view save

user output
`escaped escaped escaped 832606240 530619380 ...` Truncated

Test 38

Group: 4

Verdict: TIME LIMIT EXCEEDED

input
`100000 25000 100000 61734 16733 18530 1 47096 33881 1 95659 47 1 90943 69095 1 ...` view save

correct output
`escaped escaped escaped escaped escaped ...` view save

user output
(empty)

Leirikisa 2

Alpine valley

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 (DualRed)