oj.uz

Submission #617901

# Submission time Handle Problem Language Result Execution time Memory
617901 2022-08-01T16:41:31 Z John3_141592 Stations (IOI20_stations) C++14
100 / 100
 900 ms 800 KB 
#include "stations.h"
#include <bits/stdc++.h>

using namespace std;

vector <int> grafo[1003];
int arr[1003],C;
bool vis[1003];

void dfs(int node,int c){
    vis[node]=true;
    if(c) arr[node]=C++;
    for(auto i:grafo[node]) if(!vis[i]) dfs(i,c^1);
    if(!c) arr[node]=C++;
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v) {
    for(int i=0;i<n;i++) grafo[i].clear();
    for(int i=0;i<n-1;i++) grafo[u[i]].push_back(v[i]),grafo[v[i]].push_back(u[i]);
    fill(arr,arr+n+1,0);
    fill(vis,vis+n+1,false);
    C=0,dfs(0,0);
    vector <int> solve;
    for(int i=0;i<n;i++) solve.push_back(arr[i]);
    return solve;
}

int find_next_station(int s, int t, std::vector<int> c) {
    for(auto i:c) if(i==t) return t;
    if(s<c[0]){
        if(t<s) return c.back();
        for(auto i:c) if(i>=t) return i;
        return c.back();
    }
    if(t>s) return c[0];
    for(int i=c.size()-1;i>=0;i--) if(c[i]<=t) return c[i];
    return c[0];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 636 KB Output is correct
2 Correct 450 ms 528 KB Output is correct
3 Correct 872 ms 516 KB Output is correct
4 Correct 682 ms 416 KB Output is correct
5 Correct 581 ms 416 KB Output is correct
6 Correct 386 ms 544 KB Output is correct
7 Correct 346 ms 532 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 4 ms 504 KB Output is correct
10 Correct 0 ms 500 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 528 KB Output is correct
2 Correct 508 ms 548 KB Output is correct
3 Correct 764 ms 416 KB Output is correct
4 Correct 638 ms 420 KB Output is correct
5 Correct 594 ms 416 KB Output is correct
6 Correct 467 ms 672 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 519 ms 528 KB Output is correct
2 Correct 420 ms 644 KB Output is correct
3 Correct 751 ms 416 KB Output is correct
4 Correct 571 ms 416 KB Output is correct
5 Correct 603 ms 420 KB Output is correct
6 Correct 349 ms 548 KB Output is correct
7 Correct 407 ms 532 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 500 KB Output is correct
10 Correct 0 ms 596 KB Output is correct
11 Correct 522 ms 508 KB Output is correct
12 Correct 408 ms 660 KB Output is correct
13 Correct 458 ms 652 KB Output is correct
14 Correct 437 ms 524 KB Output is correct
15 Correct 49 ms 572 KB Output is correct
16 Correct 67 ms 584 KB Output is correct
17 Correct 97 ms 672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 540 KB Output is correct
2 Correct 644 ms 416 KB Output is correct
3 Correct 617 ms 420 KB Output is correct
4 Correct 2 ms 496 KB Output is correct
5 Correct 7 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 579 ms 524 KB Output is correct
8 Correct 820 ms 416 KB Output is correct
9 Correct 595 ms 416 KB Output is correct
10 Correct 564 ms 420 KB Output is correct
11 Correct 5 ms 492 KB Output is correct
12 Correct 5 ms 492 KB Output is correct
13 Correct 3 ms 500 KB Output is correct
14 Correct 3 ms 488 KB Output is correct
15 Correct 1 ms 500 KB Output is correct
16 Correct 481 ms 420 KB Output is correct
17 Correct 486 ms 528 KB Output is correct
18 Correct 501 ms 416 KB Output is correct
19 Correct 530 ms 532 KB Output is correct
20 Correct 462 ms 420 KB Output is correct

Subtask #5
61.0 / 61.0

# Verdict Execution time Memory Grader output
1 Correct 503 ms 548 KB Output is correct
2 Correct 411 ms 528 KB Output is correct
3 Correct 780 ms 532 KB Output is correct
4 Correct 591 ms 544 KB Output is correct
5 Correct 495 ms 416 KB Output is correct
6 Correct 423 ms 536 KB Output is correct
7 Correct 412 ms 540 KB Output is correct
8 Correct 3 ms 500 KB Output is correct
9 Correct 4 ms 492 KB Output is correct
10 Correct 0 ms 492 KB Output is correct
11 Correct 438 ms 544 KB Output is correct
12 Correct 432 ms 548 KB Output is correct
13 Correct 845 ms 420 KB Output is correct
14 Correct 579 ms 416 KB Output is correct
15 Correct 544 ms 420 KB Output is correct
16 Correct 450 ms 512 KB Output is correct
17 Correct 601 ms 532 KB Output is correct
18 Correct 429 ms 640 KB Output is correct
19 Correct 469 ms 660 KB Output is correct
20 Correct 413 ms 548 KB Output is correct
21 Correct 62 ms 620 KB Output is correct
22 Correct 78 ms 572 KB Output is correct
23 Correct 94 ms 676 KB Output is correct
24 Correct 4 ms 492 KB Output is correct
25 Correct 3 ms 500 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 500 KB Output is correct
28 Correct 1 ms 500 KB Output is correct
29 Correct 480 ms 532 KB Output is correct
30 Correct 442 ms 536 KB Output is correct
31 Correct 458 ms 528 KB Output is correct
32 Correct 479 ms 420 KB Output is correct
33 Correct 476 ms 420 KB Output is correct
34 Correct 342 ms 608 KB Output is correct
35 Correct 434 ms 760 KB Output is correct
36 Correct 448 ms 744 KB Output is correct
37 Correct 410 ms 660 KB Output is correct
38 Correct 423 ms 692 KB Output is correct
39 Correct 435 ms 768 KB Output is correct
40 Correct 368 ms 644 KB Output is correct
41 Correct 423 ms 672 KB Output is correct
42 Correct 71 ms 548 KB Output is correct
43 Correct 91 ms 720 KB Output is correct
44 Correct 123 ms 568 KB Output is correct
45 Correct 148 ms 528 KB Output is correct
46 Correct 326 ms 544 KB Output is correct
47 Correct 304 ms 724 KB Output is correct
48 Correct 43 ms 764 KB Output is correct
49 Correct 51 ms 800 KB Output is correct