CSES - Siperia opettaa 5.0

CSES - Siperia opettaa 5.0 - Results

Submission details
Task:	HDRF
Sender:	Pohjantahti
Submission time:	2017-03-09 14:46:00 +0200
Language:	C++
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	100

Test results
test	verdict	time
#1	ACCEPTED	0.04 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.05 s	details
#4	ACCEPTED	0.06 s	details
#5	ACCEPTED	0.06 s	details
#6	ACCEPTED	0.05 s	details
#7	ACCEPTED	0.06 s	details
#8	ACCEPTED	0.03 s	details
#9	ACCEPTED	0.06 s	details
#10	ACCEPTED	0.05 s	details
#11	ACCEPTED	0.03 s	details
#12	ACCEPTED	0.05 s	details
#13	ACCEPTED	0.05 s	details
#14	ACCEPTED	0.05 s	details
#15	ACCEPTED	0.04 s	details
#16	ACCEPTED	0.05 s	details
#17	ACCEPTED	0.05 s	details
#18	ACCEPTED	0.05 s	details
#19	ACCEPTED	0.05 s	details
#20	ACCEPTED	0.04 s	details
#21	ACCEPTED	0.05 s	details
#22	ACCEPTED	0.06 s	details
#23	ACCEPTED	0.05 s	details
#24	ACCEPTED	0.04 s	details
#25	ACCEPTED	0.06 s	details
#26	ACCEPTED	0.04 s	details
#27	ACCEPTED	0.05 s	details
#28	ACCEPTED	0.04 s	details
#29	ACCEPTED	0.06 s	details
#30	ACCEPTED	0.05 s	details
#31	ACCEPTED	0.05 s	details
#32	ACCEPTED	0.04 s	details
#33	ACCEPTED	0.05 s	details
#34	ACCEPTED	0.06 s	details
#35	ACCEPTED	0.06 s	details
#36	ACCEPTED	0.05 s	details
#37	ACCEPTED	0.05 s	details
#38	ACCEPTED	0.06 s	details
#39	ACCEPTED	0.06 s	details
#40	ACCEPTED	0.05 s	details
#41	ACCEPTED	0.06 s	details
#42	ACCEPTED	0.06 s	details
#43	ACCEPTED	0.05 s	details
#44	ACCEPTED	0.04 s	details
#45	ACCEPTED	0.06 s	details
#46	ACCEPTED	0.05 s	details
#47	ACCEPTED	0.04 s	details
#48	ACCEPTED	0.05 s	details
#49	ACCEPTED	0.05 s	details
#50	ACCEPTED	0.04 s	details
#51	ACCEPTED	0.06 s	details
#52	ACCEPTED	0.05 s	details
#53	ACCEPTED	0.20 s	details
#54	ACCEPTED	0.20 s	details
#55	ACCEPTED	0.20 s	details
#56	ACCEPTED	0.22 s	details
#57	ACCEPTED	0.20 s	details
#58	ACCEPTED	0.24 s	details
#59	ACCEPTED	0.19 s	details
#60	ACCEPTED	0.20 s	details
#61	ACCEPTED	0.21 s	details
#62	ACCEPTED	0.14 s	details
#63	ACCEPTED	0.15 s	details

Code

#include <iostream>
#include <set>
#include <algorithm>
#include <stack>
#include <vector>

using namespace std;

const int N = 1<<19;
const int INF = 1000000005;

int n;
int st[2*N];

int pton[100005]; // priority -> node number
int ntop[100005]; // node -> priority

set<int> g[100005];
int parent[100005];

int v[100005];

int stind = 0;

set<int> ntind[100005]; // all n ind in n arr

vector<int> res;

void muuta(int k, int x) {
    k += N;
    st[k] = x;
    for (k /= 2; k >= 1; k /= 2) {
        st[k] = min(st[2*k], st[2*k+1]);
    }
}

// get smallest priority
int rmq(int a, int b) {
    a += N;
    b += N;
    int cmin = INF;
    while (a <= b) {
        if (a%2 == 1) cmin = min(cmin, st[a++]);
        if (b%2 == 0) cmin = min(cmin, st[b--]);
        a /= 2;
        b /= 2;
    }
    return cmin;
}

void addn(int s) {
    muuta(stind, ntop[s]);
    ntind[s].insert(stind);
    stind++;
}

void dfs(int s) {
    if (v[s]) return;
    v[s] = 1;
    
    addn(s);
    
    for (int a : g[s]) {
        dfs(a);
    }
    if (g[s].size() != 0) addn(s);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 0; i < n-1; ++i) {
        int pi;
        cin >> pi;
        g[pi].insert(i+2);
        parent[i+2] = pi;
    }
    for (int i = 1; i <= n; ++i) {
        int cv;
        cin >> cv;
        pton[cv] = i;
        ntop[i] = cv;
    }
    
    dfs(1);
    
    // DEBUG
    /*for (int i = 0; i <= 6; ++i) {
        cout << rmq(i, i) << endl;
    }*/
    
    int nleft = n;
    stack<int> smstack;
    smstack.push(1);
    
    while (nleft > 0) {
        int cnode = smstack.top();
        //cout << "cnode: " << cnode << endl;
        while (g[cnode].size() != 0) {
            int clo = *(ntind[cnode].begin());
            int chi = *(--ntind[cnode].end());
            
            int mpr = rmq(clo+1, chi-1); // min pr in nd arr
            
            //cout << "rmq(" << clo+1 << ", " << chi-1 << "): " << mpr << endl;
            int nind = pton[mpr];
            smstack.push(nind);
            cnode = nind; // node label
        }
        // nyt remove
        //cout << "cnode: " << cnode << ", remove" << endl;
        
        res.push_back(cnode);
        g[parent[cnode]].erase(cnode);
        for (int a : ntind[cnode]) {
            //cout << "set " << a << " to INF" << endl;
            muuta(a, INF);
        }
        smstack.pop();
        //cout << "ST dump: " <<endl;
        //for (int i = 0; i < 25; ++i) cout << st[i] << " ";
        //cout << endl;
        nleft--;
    }
    for (int a : res) cout << a << " ";
    cout << "\n";
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`2 1 1 2` view save

correct output
`2 1` view save

user output
`2 1` view save

Test 2

Verdict: ACCEPTED

input
`100 85 42 34 7 48 48 63 90 37 80 2...` view save

correct output
`95 2 85 65 59 8 36 24 82 71 61...` view save

user output
`95 2 85 65 59 8 36 24 82 71 61...` view save

Test 3

Verdict: ACCEPTED

input
`100 14 35 99 80 25 28 11 70 24 51 ...` view save

correct output
`72 77 43 9 93 49 70 13 69 66 7...` view save

user output
`72 77 43 9 93 49 70 13 69 66 7...` view save

Test 4

Verdict: ACCEPTED

input
`100 60 55 18 87 58 26 35 17 48 9 8...` view save

correct output
`89 77 39 93 49 64 56 38 74 80 ...` view save

user output
`89 77 39 93 49 64 56 38 74 80 ...` view save

Test 5

Verdict: ACCEPTED

input
`100 57 68 23 81 85 54 62 73 100 10...` view save

correct output
`10 11 100 40 58 86 67 28 26 51...` view save

user output
`10 11 100 40 58 86 67 28 26 51...` view save

Test 6

Verdict: ACCEPTED

input
`100 33 22 18 33 26 31 57 23 93 97 ...` view save

correct output
`60 100 4 10 76 50 71 94 17 20 ...` view save

user output
`60 100 4 10 76 50 71 94 17 20 ...` view save

Test 7

Verdict: ACCEPTED

input
`200 87 30 52 56 164 149 193 82 188...` view save

correct output
`191 178 85 36 55 35 43 3 30 97...` view save

user output
`191 178 85 36 55 35 43 3 30 97...` view save

Test 8

Verdict: ACCEPTED

input
`200 3 59 148 66 188 81 172 152 170...` view save

correct output
`115 121 107 74 151 91 80 118 2...` view save

user output
`115 121 107 74 151 91 80 118 2...` view save

Test 9

Verdict: ACCEPTED

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

correct output
`3 2 4 5 1` view save

user output
`3 2 4 5 1` view save

Test 10

Verdict: ACCEPTED

input
`200 158 82 152 26 46 191 100 180 2...` view save

correct output
`13 181 18 163 24 130 2 158 184...` view save

user output
`13 181 18 163 24 130 2 158 184...` view save

Test 11

Verdict: ACCEPTED

input
`200 197 134 27 109 102 77 30 71 14...` view save

correct output
`112 144 12 131 64 137 175 117 ...` view save

user output
`112 144 12 131 64 137 175 117 ...` view save

Test 12

Verdict: ACCEPTED

input
`200 101 78 128 55 9 78 35 87 56 6 ...` view save

correct output
`197 138 177 126 68 147 145 73 ...` view save

user output
`197 138 177 126 68 147 145 73 ...` view save

Test 13

Verdict: ACCEPTED

input
`300 259 151 284 164 193 153 20 153...` view save

correct output
`63 240 115 257 206 66 42 113 2...` view save

user output
`63 240 115 257 206 66 42 113 2...` view save

Test 14

Verdict: ACCEPTED

input
`300 127 280 20 1 186 215 59 101 25...` view save

correct output
`10 257 179 56 174 135 42 169 2...` view save

user output
`10 257 179 56 174 135 42 169 2...` view save

Test 15

Verdict: ACCEPTED

input
`300 81 283 149 69 227 39 144 70 28...` view save

correct output
`207 54 241 126 151 138 118 51 ...` view save

user output
`207 54 241 126 151 138 118 51 ...` view save

Test 16

Verdict: ACCEPTED

input
`300 12 265 12 226 196 226 179 185 ...` view save

correct output
`220 198 242 11 256 125 212 174...` view save

user output
`220 198 242 11 256 125 212 174...` view save

Test 17

Verdict: ACCEPTED

input
`300 91 60 106 191 300 27 191 10 28...` view save

correct output
`247 142 103 178 256 9 154 16 8...` view save

user output
`247 142 103 178 256 9 154 16 8...` view save

Test 18

Verdict: ACCEPTED

input
`400 331 329 307 121 72 279 344 213...` view save

correct output
`346 367 343 332 11 100 44 77 1...` view save

user output
`346 367 343 332 11 100 44 77 1...` view save

Test 19

Verdict: ACCEPTED

input
`400 305 158 217 151 291 189 338 26...` view save

correct output
`114 319 34 163 183 13 175 87 3...` view save

user output
`114 319 34 163 183 13 175 87 3...` view save

Test 20

Verdict: ACCEPTED

input
`400 354 21 151 275 188 159 154 328...` view save

correct output
`232 184 314 111 112 227 393 5 ...` view save

user output
`232 184 314 111 112 227 393 5 ...` view save

Test 21

Verdict: ACCEPTED

input
`400 279 376 349 253 29 112 157 110...` view save

correct output
`131 226 382 240 276 66 136 190...` view save

user output
`131 226 382 240 276 66 136 190...` view save

Test 22

Verdict: ACCEPTED

input
`400 370 349 95 374 373 220 187 223...` view save

correct output
`269 29 129 266 222 394 395 275...` view save

user output
`269 29 129 266 222 394 395 275...` view save

Test 23

Verdict: ACCEPTED

input
`500 55 153 455 345 272 93 24 440 4...` view save

correct output
`69 104 10 499 433 251 337 470 ...` view save

user output
`69 104 10 499 433 251 337 470 ...` view save

Test 24

Verdict: ACCEPTED

input
`500 297 2 308 68 421 288 151 117 3...` view save

correct output
`494 444 419 370 107 261 439 16...` view save

user output
`494 444 419 370 107 261 439 16...` view save

Test 25

Verdict: ACCEPTED

input
`500 448 452 207 81 168 458 431 499...` view save

correct output
`445 117 188 206 156 438 321 13...` view save

user output
`445 117 188 206 156 438 321 13...` view save

Test 26

Verdict: ACCEPTED

input
`500 462 261 399 462 328 277 22 319...` view save

correct output
`73 258 171 245 148 181 110 297...` view save

user output
`73 258 171 245 148 181 110 297...` view save

Test 27

Verdict: ACCEPTED

input
`500 344 249 220 264 277 322 90 164...` view save

correct output
`36 419 257 318 414 355 179 107...` view save

user output
`36 419 257 318 414 355 179 107...` view save

Test 28

Verdict: ACCEPTED

input
`600 518 98 32 91 331 69 562 488 31...` view save

correct output
`438 286 235 368 340 354 338 39...` view save

user output
`438 286 235 368 340 354 338 39...` view save

Test 29

Verdict: ACCEPTED

input
`600 107 462 245 156 410 126 414 28...` view save

correct output
`116 194 344 560 59 337 543 233...` view save

user output
`116 194 344 560 59 337 543 233...` view save

Test 30

Verdict: ACCEPTED

input
`600 158 283 486 462 491 341 528 83...` view save

correct output
`581 301 19 557 374 433 396 278...` view save

user output
`581 301 19 557 374 433 396 278...` view save

Test 31

Verdict: ACCEPTED

input
`600 222 353 470 77 426 573 201 36 ...` view save

correct output
`346 194 423 385 43 161 373 154...` view save

user output
`346 194 423 385 43 161 373 154...` view save

Test 32

Verdict: ACCEPTED

input
`600 563 593 20 438 30 525 291 199 ...` view save

correct output
`275 171 292 426 133 136 285 21...` view save

user output
`275 171 292 426 133 136 285 21...` view save

Test 33

Verdict: ACCEPTED

input
`700 578 320 44 92 179 368 524 61 5...` view save

correct output
`127 21 504 411 619 214 103 230...` view save

user output
`127 21 504 411 619 214 103 230...` view save

Test 34

Verdict: ACCEPTED

input
`700 172 367 171 680 68 431 90 465 ...` view save

correct output
`336 263 10 104 370 572 544 173...` view save

user output
`336 263 10 104 370 572 544 173...` view save

Test 35

Verdict: ACCEPTED

input
`700 592 485 633 263 13 500 234 164...` view save

correct output
`580 329 635 17 574 191 672 280...` view save

user output
`580 329 635 17 574 191 672 280...` view save

Test 36

Verdict: ACCEPTED

input
`700 281 479 279 98 11 309 125 538 ...` view save

correct output
`509 340 171 226 298 317 16 200...` view save

user output
`509 340 171 226 298 317 16 200...` view save

Test 37

Verdict: ACCEPTED

input
`700 129 142 226 50 471 445 533 580...` view save

correct output
`69 96 324 645 208 167 652 431 ...` view save

user output
`69 96 324 645 208 167 652 431 ...` view save

Test 38

Verdict: ACCEPTED

input
`800 299 797 180 295 481 278 317 59...` view save

correct output
`149 251 709 708 421 733 798 24...` view save

user output
`149 251 709 708 421 733 798 24...` view save

Test 39

Verdict: ACCEPTED

input
`800 61 61 439 356 175 216 137 325 ...` view save

correct output
`792 30 44 426 502 39 390 264 3...` view save

user output
`792 30 44 426 502 39 390 264 3...` view save

Test 40

Verdict: ACCEPTED

input
`800 310 772 726 621 51 556 795 711...` view save

correct output
`318 161 733 86 72 271 483 670 ...` view save

user output
`318 161 733 86 72 271 483 670 ...` view save

Test 41

Verdict: ACCEPTED

input
`800 24 46 39 770 278 218 657 362 7...` view save

correct output
`566 303 132 186 47 504 78 356 ...` view save

user output
`566 303 132 186 47 504 78 356 ...` view save

Test 42

Verdict: ACCEPTED

input
`800 166 688 171 741 50 312 299 562...` view save

correct output
`119 186 291 331 48 603 575 162...` view save

user output
`119 186 291 331 48 603 575 162...` view save

Test 43

Verdict: ACCEPTED

input
`900 793 286 814 824 112 575 524 54...` view save

correct output
`40 835 125 199 491 175 355 624...` view save

user output
`40 835 125 199 491 175 355 624...` view save

Test 44

Verdict: ACCEPTED

input
`900 86 520 750 436 711 598 268 322...` view save

correct output
`485 569 557 653 321 748 277 12...` view save

user output
`485 569 557 653 321 748 277 12...` view save

Test 45

Verdict: ACCEPTED

input
`900 3 211 842 343 877 364 381 214 ...` view save

correct output
`335 639 155 81 727 888 416 752...` view save

user output
`335 639 155 81 727 888 416 752...` view save

Test 46

Verdict: ACCEPTED

input
`900 685 497 629 389 831 507 57 228...` view save

correct output
`425 843 342 667 650 180 448 57...` view save

user output
`425 843 342 667 650 180 448 57...` view save

Test 47

Verdict: ACCEPTED

input
`900 158 489 267 475 847 29 542 314...` view save

correct output
`467 792 741 221 125 49 266 887...` view save

user output
`467 792 741 221 125 49 266 887...` view save

Test 48

Verdict: ACCEPTED

input
`1000 588 544 250 749 769 456 423 98...` view save

correct output
`329 138 847 4 250 240 598 786 ...` view save

user output
`329 138 847 4 250 240 598 786 ...` view save

Test 49

Verdict: ACCEPTED

input
`1000 998 174 882 645 585 920 107 17...` view save

correct output
`180 42 847 338 228 166 612 827...` view save

user output
`180 42 847 338 228 166 612 827...` view save

Test 50

Verdict: ACCEPTED

input
`1000 805 235 974 610 433 854 903 20...` view save

correct output
`126 86 658 500 711 231 921 615...` view save

user output
`126 86 658 500 711 231 921 615...` view save

Test 51

Verdict: ACCEPTED

input
`1000 598 148 206 204 622 95 358 928...` view save

correct output
`296 283 952 288 354 907 915 77...` view save

user output
`296 283 952 288 354 907 915 77...` view save

Test 52

Verdict: ACCEPTED

input
`1000 490 683 469 136 805 544 246 51...` view save

correct output
`31 957 649 565 32 475 315 811 ...` view save

user output
`31 957 649 565 32 475 315 811 ...` view save

Test 53

Verdict: ACCEPTED

input
`100000 4944 311 69209 28682 87084 233...` view save

correct output
`78792 8393 13826 63615 17735 1...` view save

user output
`78792 8393 13826 63615 17735 1...` view save

Test 54

Verdict: ACCEPTED

input
`100000 34704 25911 59988 65186 29855 ...` view save

correct output
`44265 90477 6685 27459 49090 5...` view save

user output
`44265 90477 6685 27459 49090 5...` view save

Test 55

Verdict: ACCEPTED

input
`100000 32646 4868 34091 77349 54878 6...` view save

correct output
`69142 94411 68862 51664 42109 ...` view save

user output
`69142 94411 68862 51664 42109 ...` view save

Test 56

Verdict: ACCEPTED

input
`100000 50383 56465 63211 49461 99139 ...` view save

correct output
`95420 71427 95626 67011 82375 ...` view save

user output
`95420 71427 95626 67011 82375 ...` view save

Test 57

Verdict: ACCEPTED

input
`100000 94540 25313 57758 7201 51119 4...` view save

correct output
`79187 70032 63831 69384 51604 ...` view save

user output
`79187 70032 63831 69384 51604 ...` view save

Test 58

Verdict: ACCEPTED

input
`100000 14300 28427 96935 52311 13463 ...` view save

correct output
`5395 57047 3087 83662 90503 24...` view save

user output
`5395 57047 3087 83662 90503 24...` view save

Test 59

Verdict: ACCEPTED

input
`100000 14543 20265 6813 97256 2007 32...` view save

correct output
`16434 64136 27052 56089 37320 ...` view save

user output
`16434 64136 27052 56089 37320 ...` view save

Test 60

Verdict: ACCEPTED

input
`100000 87233 22493 10433 86194 52186 ...` view save

correct output
`62003 25428 66260 57053 59291 ...` view save

user output
`62003 25428 66260 57053 59291 ...` view save

Test 61

Verdict: ACCEPTED

input
`100000 83612 41781 34903 19741 34951 ...` view save

correct output
`29843 44886 70357 52228 52247 ...` view save

user output
`29843 44886 70357 52228 52247 ...` view save

Test 62

Verdict: ACCEPTED

input
`99995 1 2 2 4 4 6 6 8 8 10 10 12 12 ...` view save

correct output
`99995 49998 99994 49997 99993 ...` view save

user output
`99995 49998 99994 49997 99993 ...` view save

Test 63

Verdict: ACCEPTED

input
`100000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

correct output
`100000 99999 99998 99997 99996...` view save

user output
`100000 99999 99998 99997 99996...` view save

Siperia opettaa 5.0

HDRF

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

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Test 63

Tasks

Submissions (Pohjantahti)